Grokking the Coding Interview: Patterns for Coding Questions

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!
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)
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
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
I

Ike Nwankwo

· 3 years ago

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

Show 1 reply
Divya siddam

Divya siddam

· a year 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)
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

Pavel Fateev

Pavel Fateev

· a year ago

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

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);

}

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 1 reply