Lets Code Them Up!

Backspace String Compare

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. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S and T only contain lowercase letters and '#' characters.

Solution

The solution is pretty simple to this one. We need to process each String and then compare the end result. To process each string we can use Stack, push an element is its not “#”, else pop the last element. Both time and space complexity for this solution will be O(m+n), if m and n are string lengths.

class BackSpaceStringCompare {
    public boolean backspaceCompare(String S, String T) {
        
        // Find the string after processing both S and T and compare them
        return processString(S).equals(processString(T));
    }
    
    public String processString(String S){
        
        //Initialize a stack
        Stack<Character> s = new Stack<>();
        
        //Traverse through the String one character at a time
        for(char ch: S.toCharArray()){
            
            //if character is equal to #, then pop an element if stack is not empty
            if(ch == '#'){
                if(!s.isEmpty())
                    s.pop();
            }
            
            // else push character to stack
            else
                s.push(ch);
        }
        
        //return the string generated by stack
        return s.toString();
    }
}

Code – BackSpaceStringCompare.java

Source – leetcode

Megha

,
, ,