backspace string compare leetcode 解説

Goでの実装。

正直難しいし、問題の意味も最初は理解できなかった。

問題：

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

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

まず、問題文をよみとこう。 要するに#はbackspaceである。すなわち#があれば1つ前の文字は削除することとなる。

ex) abc#d なら#の前はcなので => abdになる。 ex) abcc##de# なら => abdとなる。(ccとeは削除) #は一個削除 ##は２個削除となる。

最終的にTとSが完全一致ならtrue 一致しなければfalseを返す問題。

で、このコードも自分で考えきれなかったので人のを拝借。 すごいコードを書く人もいるもんだなぁとしみじみ。

func backspaceCompare(S string, T string) bool {
    return dec(S) == dec(T)
        //ここでSとTが一致しているか確認
}


(仮にab#cなら)
func dec(T string) string { //decは文字列から#を除く処理
    for i := 0; i < len(T); i++ {
        if T[i] == '#' { 
            if i > 0 {//iが最初の要素以外なら
                T = T[:i-1] + T[i+1:]  
                                  //                                         b       #                     a       c
                                  //ab#cの時 => acにする([1]と[2]を消して、[0]と[1]のみにする。)
                i -= 2
            } else { //iが0なら
                                  //#が二つ続いている時を想定していると思う
                T = T[:i] + T[i+1:]
                i--
            }
        }
    }
    return T
}

数をこなしていこう。数が大切だ。

今回の学習点： shift unshiftの勉強になった。 sliceからの自己削除をすればいいと学んだ。