Porównanie ciągów Backspace

Poziom trudności Łatwo
Często zadawane pytania Amazonka KodNation Facebook Google Microsoft wyrocznia
Stos sznur Dwa wskaźniki Dwa wskaźnikiodwiedzajacy 124

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W zadaniu porównywania łańcuchów backspace podaliśmy dwa Smyczki S i T, sprawdź, czy są równe, czy nie. Zwróć uwagę, że ciągi zawierają znak „#”, który oznacza znak cofania.

Przykłady

Wkład
S = „ab # c”
T = „ad # c”
Wydajność
prawda (ponieważ zarówno S, jak i T konwertują na „ac”)

Wkład
S = „ab ##”
T = „c # d #”
Wydajność
prawda (ponieważ zarówno S, jak i T są puste)

Wkład
S = „a # c”
T = „b”
Wydajność
fałsz (ponieważ S = „c” i T = „b”)

Naiwne podejście do porównywania ciągów backspace

Jest to podstawowe podejście, które zajmuje trochę więcej miejsca na rozwiązanie problemu porównywania ciągów znaków backspace. Przejdźmy do logiki, jak to rozwiązać.

Przejdź przez ciągi S i T i zreformuj oba ciągi, to znaczy usuń znaki, na które wpłynie cofnięcie.
Przykład
S = „ab # c” jest przekształcane do S = „ac”, ponieważ b jest usuwane z powodu cofnięcia

Porównanie ciągów Backspaceszpilka

Następnie porównaj dwa nowe ciągi, jeśli są równe, zwróć true w przeciwnym razie zwróć false.

Reformacja struny odbywa się w następujący sposób:

  1. Utwórz pusty stos znaków.
  2. Rozpocznij przechodzenie w ciągu od indeksu 0.
  3. Jeśli bieżący znak to „#” i stos nie jest pusty, wyjmij element ze stosu.
  4. W przeciwnym razie, jeśli bieżący znak nie jest '#', odłóż bieżący znak na stos.
  5. Po całkowitym przejściu przez strunę, stos zawiera zreformowany ciąg w odwrotnej kolejności.

Analiza złożoności dla porównania ciągów backspace

Złożoność czasowa = O (n + m), gdzie n to długość struny S, a m to długość struny T.
Złożoność przestrzeni = O (n + m)

Kod JAVA

import java.util.Stack;

public class BackspaceStringCompare {
    private static boolean backSpaceCompare(String S, String T) {
        // Reform the strings and check if they are equal
        return reform(S).equals(reform(T));
    }

    // Function to reform a string
    private static String reform(String S) {
        char sArr[] = S.toCharArray();
        // Create an empty stack
        Stack<Character> stack = new Stack<>();

        // Traverse in the string
        for (int i = 0; i < sArr.length; i++) {
            // If current character is # and stack is empty, pop out an item from stack
            if (sArr[i] == '#' && !stack.isEmpty()) {
                stack.pop();
            }
            // If current character is not #, push it into the stack
            if (sArr[i] != '#') {
                stack.push(sArr[i]);
            }
        }

        // Stack contains the string in reverse order, return the reversed string
        // As it does not affect the comparision
        return String.valueOf(stack);
    }

    public static void main(String[] args) {
        // Example 1
        System.out.println(backSpaceCompare("ab#c", "ad#c"));

        // Example 2
        System.out.println(backSpaceCompare("ab##", "c#d#"));

        // Example 3
        System.out.println(backSpaceCompare("a#c", "b"));
    }
}

Kod C ++

#include <bits/stdc++.h>
using namespace std;

// Function to reform a string
string reform(char *s, int n) {
    // Create an empty stack
    stack<char> st;
    
    // Traverse in the string
    for (int i = 0; i < n; i++) {
        // If current character is # and stack is empty, pop out an item from stack
        if (s[i] == '#' && !st.empty()) {
            st.pop();
        }
        // If current character is not #, push it into the stack
        if (s[i] != '#') {
            st.push(s[i]);
        }
    }
    
    // Stack contains the string in reverse order, return the reversed string
    // As it does not affect the comparision
    char str[st.size()];
    for (int i = 0; i < st.size(); i++) {
        str[i] = st.top();
        st.pop();
    }
    
    string ans = str;
    return ans;
}

bool backSpaceCompare(char *s, char *t, int n, int m) {
    // Reform the strings and check if they are equal
    if (reform(s, n).compare(reform(t, m)) == 0) {
        return true;
    }
    return false;
}

int main() {
    // Example 1
    if (backSpaceCompare("ab#c", "ad#c", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    if (backSpaceCompare("ab##", "c#d#", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    if (backSpaceCompare("a#c", "b", 3, 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
S = "ab#c"
T = "ad#c"
true

Optymalne podejście do porównywania ciągów znaków backspace

Złożoność czasowa naiwnego podejścia nie może być dalej redukowana, ale złożoność przestrzeni można zoptymalizować do O (1).

Przechodź przez ciągi S i T w odwrotnej kolejności, jeśli zobaczymy znak backspace („#”) w którymkolwiek z ciągów, następny znak tego łańcucha niebędący znakiem backspace jest pomijany, a my porównujemy tylko niepominięte znaki.

  1. Zainicjuj dwie liczby całkowite sSkip i tSkip, które przechowują liczbę napotkanych znaków cofania.
  2. Jeśli widzimy „#” w S, inkrementuj sSkip, a jeśli widzimy „#” w T inkrementuj tSkip.
  3. Jeśli sSkip i tSkip mają wartość 0, porównaj bieżący znak ciągów S i T, jeśli są równe, kontynuuj dla pozostałego ciągu, w przeciwnym razie zwróć false.
  4. W przeciwnym razie, jeśli sSkip nie jest zerem, pomiń bieżący znak w S i zmniejsz sSkip o 1, podobnie, jeśli tSkip nie jest równe zero, pomiń bieżący znak w T i zmniejsz tSkip o 1.
  5. Powtarzaj powyższe kroki, aż w całości przejdziemy przez jedną ze strun.
  6. Dla pozostałych znaków łańcucha S, jeśli bieżącym znakiem jest '#', zwiększ sSkip o 1, w przeciwnym razie zmniejsz go o 1. Jeśli w dowolnym momencie sSkip stanie się ujemne, zwróć false.
  7. Dla pozostałych znaków łańcucha T, jeśli bieżącym znakiem jest '#', zwiększ tSkip o 1, w przeciwnym razie zmniejsz o 1. Jeśli w dowolnym momencie tSkip stanie się ujemne, zwróć false.
  8. Jeśli powyższe warunki są bezpiecznie spełnione (to znaczy bez zwracania fałszu), zwraca wartość true.

Analiza złożoności dla porównania ciągów backspace

Złożoność czasowa = O (m + n), gdzie n jest długością struny S, a m jest długością struny T.
Złożoność przestrzeni = O (1)

Kod JAVA

public class BackspaceStringCompare {
    private static boolean backSpaceCompare(String S, String T) {
        char sArr[] = S.toCharArray();
        char tArr[] = T.toCharArray();

        int sP = sArr.length - 1;
        int tP = tArr.length - 1;
        // Initialize sSkip and tSkip as 0
        int sSkip = 0;
        int tSkip = 0;

        // Traverse the strings in reverse order
        while (sP >= 0 && tP >= 0) {
            // If current character in S is '#', increment sSkip
            if (sArr[sP] == '#') {
                sSkip++;
                sP--;
            }

            // If current character in T is '#', increment tSkip
            if (tArr[tP] == '#') {
                tSkip++;
                tP--;
            }

            // If the traversal for any one string is complete break the loop
            if (sP < 0 || tP < 0) {
                break;
            }

            // If both sSkip and tSkip are zero compare the current characters
            if (sSkip == 0 && tSkip == 0) {
                if (sArr[sP] == tArr[tP]) {
                    // Continue if these are equal
                    sP--;
                    tP--;
                } else {
                    // Else return false immediately
                    return false;
                }
            } else {
                // If current character in S is '#', increment sSkip
                if (sArr[sP] == '#') {
                    sSkip++;
                    sP--;
                } else {
                    // If sSkip is not 0, skip the current character
                    if (sSkip != 0) {
                        sSkip--;
                        sP--;
                    }
                }

                // If current character in T is '#', increment tSkip
                if (tArr[tP] == '#') {
                    tSkip++;
                    tP--;
                } else {
                    // If tSkip is not 0, skip the current character
                    if (tSkip != 0) {
                        tSkip--;
                        tP--;
                    }
                }
            }
        }

        // Traverse the remaining S string
        while (sP >= 0) {
            // If current character is '#', increment sSkip
            if (sArr[sP] == '#') {
                sSkip++;
            } else {
                // Else decrement sSkip
                sSkip--;
            }

            // If sSkip becomes negative return false
            if (sSkip < 0)
                return false;

            sP--;
        }

        // Traverse the remaining T string
        while (tP >= 0) {
            // If current character is '#', increment tSkip
            if (tArr[tP] == '#') {
                tSkip++;
            } else {
                // Else decrement tSkip
                tSkip--;
            }

            // If tSkip becomes negative, return false
            if (tSkip < 0) {
                return false;
            }

            tP--;
        }

        // Return true if encountered above cases safely
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        System.out.println(backSpaceCompare("ab#c", "ad#c"));

        // Example 2
        System.out.println(backSpaceCompare("ab##", "c#d#"));

        // Example 3
        System.out.println(backSpaceCompare("a#c", "b"));
    }
}

Kod C ++

#include <bits/stdc++.h>
using namespace std;

bool backSpaceCompare(char *S, char *T, int n, int m) {
    int sP = n - 1;
    int tP = m - 1;
    
    // Initialize sSkip and tSkip as 0
    int sSkip = 0;
    int tSkip = 0;
    
    // Traverse the strings in reverse order
    while (sP >= 0 && tP >= 0) {
        // If current character in S is '#', increment sSkip
        if (S[sP] == '#') {
            sSkip++;
            sP--;
        }
        
        // If current character in T is '#', increment tSkip
        if (T[tP] == '#') {
            tSkip++;
            tP--;
        }
        
        // If the traversal for any one string is complete break the loop
        if (sP < 0 || tP < 0) {
            break;
        }
        
        // If both sSkip and tSkip are zero compare the current characters
        if (sSkip == 0 && tSkip == 0) {
            if (S[sP] == T[tP]) {
                // Continue if these are equal
                sP--;
                tP--;
            } else {
                // Else return false immediately
                return false;
            }
        } else {
            // If current character in S is '#', increment sSkip
            if (S[sP] == '#') {
                sSkip++;
                sP--;
            } else {
                // If sSkip is not 0, skip the current character
                if (sSkip != 0) {
                    sSkip--;
                    sP--;
                }
            }
            
            // If current character in T is '#', increment tSkip
            if (T[tP] == '#') {
                tSkip++;
                tP--;
            } else {
                // If tSkip is not 0, skip the current character
                if (tSkip != 0) {
                    tSkip--;
                    tP--;
                }
            }
        }
    }
    
    // Traverse the remaining S string
    while (sP >= 0) {
        // If current character is '#', increment sSkip
        if (S[sP] == '#') {
            sSkip++;
        } else {
            // Else decrement sSkip
            sSkip--;
        }
        
        // If sSkip becomes negative return false
        if (sSkip < 0)
            return false;
        sP--;
    }
    
    // Traverse the remaining T string
    while (tP >= 0) {
        // If current character is '#', increment tSkip
        if (T[tP] == '#') {
            tSkip++;
        } else {
            // Else decrement tSkip
            tSkip--;
        }
        
        // If tSkip becomes negative, return false
        if (tSkip < 0) 
            return false;
        tP--;
    }
    
    // Return true if encountered above cases safely
    return true;
}

int main() {
    // Example 1
    if (backSpaceCompare("ab#c", "ad#c", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    if (backSpaceCompare("ab##", "c#d#", 4, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    if (backSpaceCompare("a#c", "b", 3, 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
S = "ab##"
T = "c#d#"
true

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »