844. Backspace String Compare

Stanislav Gumeniuk включен в Leetcode Leetcode-Problem

2020-04-09 324 слов 2 минуты

Содержание

Решение задачи 844 “Backspace String Compare” с LeetCode.

Условие задачи

Даны две строки S и T, необходимо вернуть результат сравнения этих строк, если воспринимать их как последовательность напечатанных символов, где # - означает backspace.

пример 1

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

пример 2

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

пример 3

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

пример 4

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

ограничения

1 <= S.length <= 200
1 <= T.length <= 200
S и T содержать только буквы в нижнем регистре и #

Решение

Brute force

Идея алгоримма

Написать метод, который будет идти по заданной строке и при встрече # удалять его и предыдущий символ( если есть).

Отправить обе входных строки в этот метод и сравнить результат

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
}

Два указателя

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
}