Check if two strings after processing backspace character are equal or not

Java Solution for Backspace String Compare

Problem Description :

Given two strings s1 and s2, in which backspaces are represented by #. The task is to determine whether the resultant strings after processing the backspace character would be equal or not.

Example 1 :

Input :
s1 = "abcd#"
s2 = "abc"

Output :
true

Explanation : s1 become "abc" after backspace d character and s2 is already "abc"

Example 2 :

Input :
s1 = "abc#"
s2 = "abc"

Output :
false

Explanation : s1 become "ab" after backspace c character and s2 is "abc"

Example 3 :

Input :
s1 = "ab##c"
s2 = "ac"

Output :
false

Explanation : s1 become "c" after backspace and s2 is "ac"

Example 4 :

Input :
s1 = "abcdefg"
s2 = "abcdefi#g"

Output :
false

Here we have to delete last character if '#' (backspace) present in given String s1 or String s2. After that compare both string and if s1 and s2 matches return true otherwise return false. 

Solution 1 : Java Code for BackSpace String Compare

import java.util.Scanner;

public class BackspaceStringCompare {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter str1 and str2 : ");
        String str1 = sc.next();
        String str2 = sc.next();

        System.out.println(backspaceCompare(str1, str2));
       
    }
    
    public static boolean backspaceCompare(String s, String t) {

        StringBuilder b1 = new StringBuilder();
        StringBuilder b2 = new StringBuilder();
       
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '#') {
                if (b1.length() !=0 ) {
                    b1.deleteCharAt(b1.length()-1);
                }
            } else {
                b1.append(s.charAt(i));
            }
        }
       
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == '#') {
                if (b2.length() != 0) {
                    b2.deleteCharAt(b2.length()-1);
                }
            } else {
                b2.append(t.charAt(i));
            }
        }
       
        return b1.toString().equals(b2.toString());
    }
}

Solution Explanation :

• Take two StringBuilder objects for String s1 and s2.
  
• Traverse through entire given string characters one by one and add String character in StringBuilder. check if backspace is present or not, If present delete last character from given StringBuilder. 
• Also check for StringBuilder length is greater than 0 otherwise it will gives error while deleting.
• Last check both string using .equals() method and return true if matches otherwise return false.

RECOMMENDED TUTORIALS :

• Java Program for Find Minimum Element in Rotated Sorted Array 
• Hacker Rank Mark and Toys Solution In Java