BackspaceStringCompare [source code]

public class BackspaceStringCompare {
static
/****************************************************************************/
class Solution {
    public boolean backspaceCompare(String S, String T) {
        return parse (S).equals (parse (T));
    }

    String parse (String s) {
        Deque<Character> stack = new ArrayDeque<> ();
        for (char c : s.toCharArray ()) {
            if (c == '#') {
                if (!stack.isEmpty ())
                    stack.poll ();
            } else {
                stack.push (c);
            }
        }
        return stack.toString ();
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        BackspaceStringCompare.Solution tester = new BackspaceStringCompare.Solution();
        String[] inputs = {
            "ab#c", "ad#c", "true",
            "ab##", "c#d#", "true",
            "a##c", "#a#c", "true",
            "a#c", "b", "false",
        };

    }
}

简单的Stack处理好像就行了;

好像不用Stack的方法应该是有的, 不过先用简单方法做做看; easy问题, 估计不会卡collection overhead;

java> String s = "abc"  
java.lang.String s = "abc"  
java> for (char c : s) System.out.println (c);

比较轻松的AC了, 过;

UNFINISHED

uwi:两分半:

class Solution {  
    public boolean backspaceCompare(String S, String T) {  
        return sim(S).equals(sim(T));  
    }  

    String sim(String s)  
    {  
        StringBuilder sb = new StringBuilder();  
        for(int i = 0;i < s.length();i++){  
            if(s.charAt(i) == '#'){  
                if(sb.length() > 0){  
                    sb.deleteCharAt(sb.length()-1);  
                }  
            }else{  
                sb.append(s.charAt(i));  
            }  
        }  
        return sb.toString();  
    }  
}

Problem Description

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.

Difficulty:Easy
Total Accepted:1.6K
Total Submissions:2.9K
Contributor:terranblake