बैकस्पेस स्ट्रिंग तुलना  


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना कोडेशन Facebook गूगल माइक्रोसॉफ्ट ओरेकल
धुआँरा तार दो सूचक दो संकेत

बैकस्पेस स्ट्रिंग में समस्या की तुलना में हमने दो दिए हैं स्ट्रिंग्स एस और टी, जांचें कि वे समान हैं या नहीं। ध्यान दें कि तार में '#' होता है जिसका अर्थ है बैकस्पेस वर्ण।

उदाहरण  

निवेश
S = "ab # c"
टी = "विज्ञापन # सी"
उत्पादन
सच (एस और टी दोनों के रूप में "एसी" में कनवर्ट करता है)

निवेश
S = "ab ##"
T = "c # d #"
उत्पादन
सच (एस और टी दोनों खाली हैं)

निवेश
S = "a # c"
टी = "बी"
उत्पादन
असत्य (S = "c" और T = "b")

बैकस्पेस स्ट्रिंग के लिए Naive दृष्टिकोण  

यह मूल दृष्टिकोण है जो बैकस्पेस स्ट्रिंग की तुलना समस्या को हल करने के लिए कुछ अतिरिक्त स्थान लेता है। आइए इसे हल करने के तर्क पर आएं।

ट्रैवर्स स्ट्रिंग्स S और T और दोनों स्ट्रिंग्स को सुधारें, अर्थात्, उन वर्णों को हटा दें जो बैकस्पेस से प्रभावित होंगे।
उदाहरण
S = "ab # c" को S = "ac" में सुधार किया जाता है, क्योंकि बैकस्पेस के कारण b को हटा दिया जाता है

बैकस्पेस स्ट्रिंग तुलनापिन

फिर, दो नए स्ट्रिंग्स की तुलना करें, यदि वे समान रिटर्न वाले हैं, तो दूसरे झूठे हैं।

एक स्ट्रिंग के लिए सुधार के रूप में किया जाता है,

  1. पात्रों का एक खाली ढेर बनाएँ।
  2. इंडेक्स 0 से स्ट्रिंग में ट्रैवर्सिंग शुरू करें।
  3. यदि वर्तमान वर्ण '# ’और है धुआँरा खाली नहीं है, स्टैक से एक आइटम पॉप आउट करें।
  4. यदि वर्तमान वर्ण '#' नहीं है, तो वर्तमान वर्ण को स्टैक में धकेलें।
  5. स्ट्रिंग को पूरी तरह से पीछे करने के बाद, स्टैक में रिवर्स ऑर्डर में सुधारित स्ट्रिंग होती है।
यह भी देखें
NGE की संख्या दाईं ओर

बैकस्पेस स्ट्रिंग के लिए जटिलता विश्लेषण की तुलना करें

समय जटिलता = O (n + m), जहां n स्ट्रिंग की लंबाई S है और M, स्ट्रिंग T की लंबाई है।
अंतरिक्ष जटिलता = O (n + m)

जावा कोड

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 ++ कोड

#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

बैकस्पेस स्ट्रिंग के लिए इष्टतम दृष्टिकोण की तुलना करें  

भोले दृष्टिकोण की समय जटिलता को और कम नहीं किया जा सकता है, लेकिन अंतरिक्ष जटिलता को ओ (1) के लिए अनुकूलित किया जा सकता है।

यह भी देखें
पाठ औचित्य

स्ट्रिंग्स S और T को उल्टे क्रम में ट्रैव करें, यदि हम किसी स्ट्रिंग में एक बैकस्पेस वर्ण ('#') देखते हैं, तो उस स्ट्रिंग का अगला गैर-बैकस्पेस वर्ण छोड़ दिया जाता है, और हम केवल गैर छोड़ दिए गए वर्णों की तुलना करते हैं।

  1. दो पूर्णांक sSkip और tSkip को आरम्भिक करें, जो सामना किए गए बैकस्पेस की संख्या को संग्रहीत करता है।
  2. यदि हम S में एक '#' देखते हैं, तो SSkip बढ़ाएँ, और अगर हम T 'वेतन वृद्धि tSkip में' # 'देखते हैं।
  3. यदि sSkip और tSkip 0 हैं, तो स्ट्रिंग्स S और T के वर्तमान वर्ण की तुलना करें, यदि ये समान हैं तो शेष स्ट्रिंग के लिए जारी रहती हैं अन्यथा गलत लौट आती हैं।
  4. यदि sSkip शून्य नहीं है, तो S में वर्तमान वर्ण छोड़ें और sSkip को 1 से घटाएं, इसी प्रकार यदि tSkip शून्य नहीं है, तो T में वर्तमान वर्ण को छोड़ें और tSkip को 1 से घटाएं।
  5. उपरोक्त चरणों को तब तक दोहराएं जब तक कि हम पूरी तरह से एक तार को पार न कर दें।
  6. स्ट्रिंग S के शेष वर्णों के लिए, यदि वर्तमान वर्ण 1 से 'srement sSkip' है, तो अन्य इसे 1 से घटाता है। यदि किसी भी समय sSkip नकारात्मक रिटर्न झूठा हो जाता है।
  7. स्ट्रिंग T के शेष वर्णों के लिए, यदि वर्तमान वर्ण 1 से 's' वृद्धि tSkip है, तो अन्य इसे 1. XNUMX से घटाता है। यदि किसी भी समय tSkip नकारात्मक रिटर्न गलत हो जाता है।
  8. यदि उपरोक्त शर्तों को सुरक्षित रूप से पारित किया गया है (जो कि झूठे वापस किए बिना है), सही लौटें।

बैकस्पेस स्ट्रिंग के लिए जटिलता विश्लेषण की तुलना करें

समय जटिलता = ओ (एम + एन), जहां n स्ट्रिंग S की लंबाई है, और मीटर स्ट्रिंग T की लंबाई है।
अंतरिक्ष जटिलता = ओ (1)

जावा कोड

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 ++ कोड

#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

संदर्भ