The Backspace String Compare Algorithm

  • 时间：2020-09-30 16:23:25
  • 分类：网络文摘
  • 阅读：143 次

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:
Input: S = “ab#c”, T = “ad#c”
Output: true
Explanation: Both S and T become “ac”.

Example 2:
Input: S = “ab##”, T = “c#d#”
Output: true
Explanation: Both S and T become “”.

Example 3:
Input: S = “a##c”, T = “#a#c”
Output: true
Explanation: Both S and T become “c”.

Example 4:
Input: S = “a#c”, T = “b”
Output: false
Explanation: S becomes “c” while T becomes “b”.

Note:
1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and ‘#’ characters. Can you solve it in O(N) time and O(1) space?

Javascript algorithm to perform backspace string comparison

To simulate the backspace key, we can use a stack, and perform a pop operation when we want to delete previous character. In Javascript, we can use Array.prototype.pop() to remove the last element (which can be called on empty array and that returns undefined). When we iterate all characters, we need to join the stack/array as a string. Then, the last step is to perform a string comparisons.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function(S, T) {
    const build = (S) => {
        let st = [];        
        for (let i = 0, len = S.length; i < len; ++ i) {
            if (S[i] == '#') {
                st.pop(); // if called on empty array, return undefined.
            } else {
                st.push(S[i]);
            }
        }
        return st.join('');
    }
    return build(S) === build(T);
};
/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function(S, T) {
    const build = (S) => {
        let st = [];        
        for (let i = 0, len = S.length; i < len; ++ i) {
            if (S[i] == '#') {
                st.pop(); // if called on empty array, return undefined.
            } else {
                st.push(S[i]);
            }
        }
        return st.join('');
    }
    return build(S) === build(T);
};

String backspace comparison in C++

Slightly differently, we do not construct/join the characters in the stack, instead, we can perform comparisons on both stacks generated from two input strings. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        stack<char> st1 = realString(S);
        stack<char> st2 = realString(T);
        if (st1.size() != st2.size()) return false;
        while (st1.size() > 0) {
            char p1 = st1.top();
            char p2 = st2.top();
            st1.pop();
            st2.pop();
            if (p1 != p2) return false;
        }
        return true;
    }
    
private:
    stack<char> realString(string S) {
        stack<char> st;    
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == '#') {
                if (st.size() > 0) {
                    st.pop();
                }
            } else {
                st.push(S[i]);
            }
        }
        return st;
    }
};
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        stack<char> st1 = realString(S);
        stack<char> st2 = realString(T);
        if (st1.size() != st2.size()) return false;
        while (st1.size() > 0) {
            char p1 = st1.top();
            char p2 = st2.top();
            st1.pop();
            st2.pop();
            if (p1 != p2) return false;
        }
        return true;
    }
    
private:
    stack<char> realString(string S) {
        stack<char> st;    
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == '#') {
                if (st.size() > 0) {
                    st.pop();
                }
            } else {
                st.push(S[i]);
            }
        }
        return st;
    }
};

Java implementation of string backspace comparisons

We can use String.valueOf(stack) to convert the stack of characters into String.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }
 
    public String build(String S) {
        Stack<Character> ans = new Stack();
        for (char c: S.toCharArray()) {
            if (c != '#')
                ans.push(c);
            else if (!ans.empty())
                ans.pop();
        }
        return String.valueOf(ans);
    }
}
class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String S) {
        Stack<Character> ans = new Stack();
        for (char c: S.toCharArray()) {
            if (c != '#')
                ans.push(c);
            else if (!ans.empty())
                ans.pop();
        }
        return String.valueOf(ans);
    }
}

All above implementations run at complexity O(M + N) in both time and space where M and N are the lengths of input strings S and T respectively.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
饮酒之道：取其益而去其害 扬长避短善用之　 秋冬季节这八种人不适合吃辣椒　 儿童不宜吃含化学合成甜味剂的食品　 十大“垃圾”食品在你家的餐桌上吗？　 让你的孩子远离“三无”劣质小零食　 网络传闻中的“致癌食物”是否真致癌　 冬季食补：最佳的羊肉吃法，你知道吗　 鸡汤虽营养丰富，但这几种病人不要喝　 饮食健康与胃病食疗（一）：胃病患者饮食注意事项　 饮食健康与胃病食疗（二）：慢性胃炎的饮食调理　
评论列表
添加评论