Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 2: Comparing Strings containing Backspaces (medium)

Problem Statement

Given two strings containing backspaces (identified by the character '#'), check if the two strings are equal.

Example 1:

Input: str1="xy#z", str2="xzz#"
Output: true
Explanation: After applying backspaces the strings become "xz" and "xz" respectively.

Example 2:

Input: str1="xy#z", str2="xyz#"
Output: false
Explanation: After applying backspaces the strings become "xz" and "xy" respectively.

Example 3:

Input: str1="xp#", str2="xyz##"
Output: true
Explanation: After applying backspaces the strings become "x" and "x" respectively.

.....

.....

.....

Like the course? Get enrolled and start learning!
Shaurya Sood

Shaurya Sood

· 6 days ago

The way I did it was not two pointer but I just created two additional strings str3 and str4 and went through and added and removed letters based on our original str1 and str2. then I compared the two new strings str3 and str4 for equivalency

class Solution {

  public static boolean compare(String str1, String str2) {

    char[] str1Arr = str1.toCharArray();
    char[] str2Arr = str2.toCharArray();

    String str3 = "";
    String str4 = "";

    for (int i = 0; i < str1Arr.length; i++) {

      if (str1Arr[i] == '#') {
        if (str3.length() > 0)
          str3 = str3.substring(0, str3.length() - 1);
      }
      else {
        str3 = str3 + str1Arr[i];
      }
    }

    for (int i = 0; i < str2Arr.length; i++) {

      if (str2Arr[i] == '#') {
        if (str4.l
Sahil Kumar

Sahil Kumar

· a year ago

class Solution {
  compare(str1, str2) {
    const s1 = this.removeHash(str1.split(''))
    const s2 = this.removeHash(str2.split(''))
    return s1 === s2
  }

  removeHash(strAr) {
    let j = -1
    for(let i=0;i<strAr.length;i+=1){
      if(strAr[i] !== "#"){
        strAr[++j] = strAr[i]
      }else{
        j-=1
        if(j < -1) j=-1
      }
    }
    return strAr.slice(0,j+1).join('')
  }
}
Show 2 replies
Denys Stopkin

Denys Stopkin

· a year ago

static std::string deleteBackspaces(const std::string& str)

{

std::string result;



for (int i = 0; i < str.size(); ++i)

{

    if (str[i] != '#')

    {

		result.push_back(str[i]);

	}

    else

    {

        if (!result.empty())

        {

            result.pop_back();

        }

    }

}



return result;

}

static bool compare(const std::string& str1, const std::string& str2)

{

return deleteBackspaces(str1) == deleteBackspaces(str2);

}

Show 1 reply
Pavel Fateev

Pavel Fateev

· a year ago

Spec says lenght of strings is >= 1 but one of the test cases tests empty string?

Show 1 reply
venkata sreekanth bhagavatula

venkata sreekanth bhagavatula

· a year ago

If anyone is confused by backspace even exists, it controls the exit from the loop. just fyi

Show 1 reply
Divya siddam

Divya siddam

· 2 years ago

class Solution:

def process(self, s):

    result = []

    for char in s:

        if char == '#':

            if result:

                result.pop()

        else:

            result.append(char)

    return ''.join(result)



def backspaceCompare(self, str1, str2):

    return self.process(str1) == self.process(str2)
Show 1 reply
K

kr.behrman

· 3 years ago

I'm confused by the last result , the input is "#a#c" "abc###" and the expected is True. Wouldn't they reduce to "c" and "" , which are not equal?

Show 3 replies
Arturo Calderón

Arturo Calderón

· 3 years ago

class Solution:
  def ApplyBackspaces(self, string):
    stack = []
    for c in string:
        if c == '#':
            if len(stack) > 0:
                stack.pop()
        else:
            stack.append(c)
    return ''.join(stack)

  def compare(self, string1, string2):
    return self.ApplyBackspaces(string1) == self.ApplyBackspaces(string2)
I

Ike Nwankwo

· 4 years ago

Couldn't this be done in O(N) where N is the length of the bigger string?

Show 1 reply
L

Lemon Ruan

· 4 years ago

regarding this line of code "if i1 < 0 and i2 < 0: # reached the end of both the strings return True" why is the condition i1

Show 5 replies

Reading Progress

0%

Vote for new content