2022/09/29

Leetcode Note: Go - Backspace String Compare

Backspace String Compare - LeetCode
https://leetcode.com/problems/backspace-string-compare/

  • Go 言語で取り組んだメモ

所感

  • string s, t が与えられ、空のテキストエディターに入力したときに、それが等しい場合は true を return する
  • # はバックスペース文字を意味する

回答

Backspace String Compare - LeetCode
https://leetcode.com/problems/backspace-string-compare/solution/

[Go] Multiple Solutions - Clean Code (0ms 100%) O((m+n)/2) - LeetCode Discuss
https://leetcode.com/problems/backspace-string-compare/discuss/1787466/Go-Multiple-Solutions-Clean-Code-(0ms-100)-O((m%2Bn)2)

// Time: O(n+m)
// Space: O(1)
func backspaceCompare(s string, t string) bool {
	// Time: O(n)
	s = stringWithoutSpace(s)

	// Tim: O(m)
	t = stringWithoutSpace(t)

    return strings.EqualFold(stringWithoutSpace(s), stringWithoutSpace(t))
}

func stringWithoutSpace(s string) string {
    sb := new(strings.Builder)
	
	// O(len(s))
    for _, r := range s {
        if r != '#' {
            sb.WriteRune(r)
        } else {
            removeLastRune(sb)
        }
    }
    return sb.String()
}

func removeLastRune(sb *strings.Builder) {
    str := sb.String()
    if len(str) > 0 {
        str = str[:len(str)-1]
        sb.Reset()
        sb.WriteString(str)
    }
}

See Also