844. Backspace String Compare

Stanislav Gumeniuk included in Leetcode Leetcode-Problem

2020-04-09 348 words 2 minutes

Contents

Automatic Translation

This article has been translated automatically from Russian to English. The original is available in Russian.

Solution to problem 844 “Backspace String Compare” from LeetCode.

Problem Statement

Given two strings S and T, return the result of comparing these strings when interpreting them as a sequence of typed characters, where # means backspace.

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".

Constraints

1 <= S.length <= 200
1 <= T.length <= 200
S and T contain only lowercase letters and #

Solution

Brute Force

Algorithm idea

Write a method that will go through a given string and when encountering # will delete it and the previous character (if any).

Send both input strings to this method and compare the result

func backspaceCompare(S string, T string) bool {
	S = clear(S)
	T = clear(T)

	return S == T
}

func clear(S string) string {
	for idx := 0; idx < len(S); idx++ {
		if string(S[idx]) != "#" {
			continue
		}
		if idx-1 >= 0 {
			S = S[:idx-1] + S[idx:]
			fmt.Println("->", idx, S)
			idx--
		}

		S = S[:idx] + S[idx+1:]
		idx--
	}
	return S
}

Two Pointers

func backspaceCompare(S string, T string) bool {
    s := len(S)-1
    t := len(T)-1
    sb := 0
    tb := 0

    for t>=0 || s>=0 {
        for s >= 0 {
            if string(S[s]) == "#" {
                sb++
                s--
            } else if sb>0 {
                sb--
                s--
            }else {
                break
            }
        }

        for t >= 0 {
            if string(T[t]) == "#" {
                tb++
                t--
            } else if tb>0 {
                tb--
                t--
            }else {
                break
            }
        }

        if s>=0 && t>= 0&& S[s]!=T[t]{
            return false
        }

        if (s>=0) != (t>=0) {
            return false
        }

        s--
        t--
    }
    return true
}