Backspace String müqayisə edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Kod milləti Facebook google microsoft Kahin
Qalaq Sim İki işarə İki işarəBaxılıb 125

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Arxa sətirdə ikisini verdiyimiz problemi müqayisə edin Strings S və T, bərabər olub olmadığını yoxlayın. Diqqət yetirin ki, sətirlərdə '#' işarəsi var, bu da geri çəkmə işarəsi deməkdir.

Nümunələr

Input
S = “ab # c”
T = “elan # c”
Buraxılış
true (həm S, həm də T "ac" a çevrildiyi üçün)

Input
S = "ab ##"
T = “c # d #”
Buraxılış
doğru (həm S, həm də T boş olduğu üçün)

Input
S = “a # c”
T = "b"
Buraxılış
yalan (S = "c" və T = "b" kimi)

Arxa sətir üçün sadəlövh yanaşma müqayisə

Bu backspace string problemini həll etmək üçün əlavə yer alan əsas yanaşmadır. Bunu necə həll etmə məntiqinə gələk.

S və T sətirlərini kəsin və hər iki sətri islah edin, yəni arxa boşluqdan təsirlənəcək simvolları silin.
misal
S = “ab # c” S = “ac” şəklində islah olunur, çünki b boşluq olduğuna görə silinir

Backspace String müqayisə edinPin

Sonra bərabər olduqda iki yeni Sətri müqayisə edin return return true return return false.

Bir simli islahat aşağıdakı kimi edilir.

  1. Boş bir simvol yığını yaradın.
  2. İndeks 0-dan sətrə keçməyə başlayın.
  3. Mövcud xarakter '#' və qalaq boş deyil, yığından bir maddə çıxarın.
  4. Cari xarakter '#' deyilsə, başqa bir halda cari xarakteri yığına itələyin.
  5. Sətri tamamilə keçdikdən sonra yığın düzəldilmiş sətri tərs qaydada ehtiva edir.

Arxa sətir müqayisəsi üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi = O (n + m), burada n - S sətrin uzunluğu, m - T sətrin uzunluğu.
Kosmik Mürəkkəblik = O (n + m)

JAVA Kodu

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"));
    }
}

C ++ kodu

#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

Arxa sətir üçün optimal yanaşma müqayisə

Sadəlövh yanaşmanın zaman mürəkkəbliyi daha da azaldıla bilməz, ancaq kosmik mürəkkəblik O (1) səviyyəsinə endirilə bilər.

S və T sətirlərini tərs qaydada keçin, hər hansı bir sətirdə bir arxa işarəsi ('#') görsək, həmin sətrin növbəti boşluq olmayan xarakteri atlanır və yalnız atılmayan simvolları müqayisə edirik.

  1. Qarşılaşılan arxa boşluqların sayını saxlayan iki tam ədədi sSkip və tSkip başlayın.
  2. S-də bir "#" görsək, sSkip artırın və T artımında bir "#" görsək tSkip.
  3. SSkip və tSkip 0 olduqda, S və T simlərinin cari xarakterini müqayisə edin, əgər bunlar bərabərdirsə, qalan sətir üçün davam edin, əks halda false qayıdın.
  4. Başqa bir halda sSkip sıfır deyilsə, S-dəki cari işarəni atlayın və sSkip-i 1-ə endirin, eyni şəkildə tSkip sıfır deyilsə, Tdakı cari xarakteri atlayın və tSkip-i 1-ə endirin.
  5. İplərdən birini tamamilə keçməyimizə qədər yuxarıdakı addımları təkrarlayın.
  6. S sətrinin qalan simvolları üçün cari simvol '#' sSkip-i 1 artırsa, başqa halda onu 1 azaldın. Əgər hər hansı bir anda sSkip mənfi qayıdırsa yalan olur.
  7. T sətrinin qalan simvolları üçün cari simvol '#' tSkip-i 1 artırsa, başqa halda onu 1 azaldın. Əgər hər an tSkip mənfi qayıdırsa yalan olur.
  8. Yuxarıdakı şərtlər etibarlı bir şəkildə keçərsə (yalan qaytarılmadan), doğru qayıdın.

Arxa sətir müqayisəsi üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi = O (m + n), burada n S simli uzunluğu, m isə simli T uzunluğu.
Kosmik Mürəkkəblik = O (1)

JAVA Kodu

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"));
    }
}

C ++ kodu

#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

References

Crack Sistemi Dizayn Müsahibələri
Translate »