退格字符串比較


難度級別 容易獎學金
經常問 亞馬遜 編碼國家 Facebook 谷歌 Microsoft微軟 神諭
兩指針 兩個指針

在退格字符串比較問題中,我們給出了兩個 字符串 S和T,檢查它們是否相等。 請注意,字符串包含“#”,表示退格字符。

範例檔案

輸入
S =“ ab#c”
T =“ ad#c”
產量
正確(因為S和T都轉換為“ ac”)

輸入
S =“ ab ##”
T =“ c#d#”
產量
正確(因為S和T均為空)

輸入
S =“ a#c”
T =“ b”
產量
假(因為S =“ c”和T =“ b”)

退格字符串比較的幼稚方法

這是基本的方法,需要一些額外的空間來解決退格字符串比較問題。 讓我們來談談解決問題的邏輯。

遍歷字符串S和T並重新格式化兩個字符串,即刪除將受退格鍵影響的字符。

S =“ ab#c”被重塑為S =“ ac”,因為由於退格而刪除了b

退格字符串比較

然後,比較兩個新的字符串,如果它們相等,則返回true,否則返回false。

字符串的重整是這樣完成的:

  1. 創建一個空字符堆棧。
  2. 從索引0開始遍歷字符串。
  3. 如果當前字符是“#”,並且 不為空,請從堆棧中彈出一個項目。
  4. 否則,如果當前字符不是'#',則將當前字符推入堆棧。
  5. 完全遍歷字符串後,堆棧將以相反的順序包含重新格式化的字符串。

退格字符串比較的複雜度分析

時間複雜度= O(n +米),其中n是字符串S的長度,m是字符串T的長度。
空間複雜度= O(n +米)

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

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

退格字符串比較的最佳方法

天真的方法的時間複雜度無法進一步降低,但是空間複雜度可以優化為O(1)。

以相反的順序遍歷字符串S和T,如果在任何字符串中看到一個退格字符('#'),則將跳過該字符串的下一個非退格字符,並且僅比較未跳過的字符。

  1. 初始化兩個整數sSkip和tSkip,它們存儲遇到的退格鍵的數量。
  2. 如果在S中看到一個“#”,則將sSkip遞增,如果在T中看到一個“#”,則將tSkip遞增。
  3. 如果sSkip和tSkip為0,則比較字符串S和T的當前字符,如果它們相等,則繼續其餘字符串,否則返回false。
  4. 否則,如果sSkip不為零,則跳過S中的當前字符並將sSkip減小1,類似地,如果tSkip不為零,則跳過T中的當前字符並將tSkip減小1。
  5. 重複上述步驟,直到我們完全遍歷其中一根弦為止。
  6. 對於字符串S的其餘字符,如果當前字符為“#”,則sSkip遞增1,否則將其遞減1。如果在任何時候sSkip變為負數,則返回false。
  7. 對於字符串T的其餘字符,如果當前字符為'#',則將tSkip遞增1,否則將其遞減1。如果在任何時候tSkip變為負數,則返回false。
  8. 如果安全地通過了上述條件(即不返回false),則返回true。

退格字符串比較的複雜度分析

時間複雜度= O(米+ n),其中n是字符串S的長度,m是字符串T的長度。
空間複雜度= O(1)

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

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

參考