2022/04/03

Leetcode Note: Go - Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode
https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

所感

  • 繰り返しが存在しているのかチェックする実装方法が思いつかない…

実装準備

func lengthOfLongestSubstring(s string) int {
    output := 0
    
    if s == nil {
        return output
    }
    
    // うーん。どうやってユニークな文字か判定すれば良いんだろう
    // 前後の文字をチェックしても xxxabcxxxdefxxx みたいなパターンを検出できない
    for i := 0; i < len(s); i++ {
        
    }
    
    return output 
}

func main() {
    input := "abcabcbb" // output: abc => 3
    // input := "bbbbb" // output: b => 1
    // input := "pwwkew" // output: kew => 3
    fmt.Println(input)
    
    output := lengthOfLongestSubstring(input)
    fmt.Println(output)
}

回答

Golang: explanation (100% speed & memory) - LeetCode Discuss
https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/441906/Golang%3A-explanation-(100-speed-and-memory)

  1. dict は以前に遭遇した文字のディクショナリ
  2. i をインクリメントして s[i] を dict のインデックスとして使用して、値を true にする
    • dict[s[i]] = true
    • これを既出の文字列か判定するためのマークにする
  3. 各ステップで length をインクリメントして max として比較して、長さが大きくなった場合は max = length を設定
  4. すでに dict でマークした文字を dict[s[i]] == true で判定した場合は、 2つ目 のイテレーターである j をインクリメントしてディクショナリ dict[s[j]] = false でマークを外して、 dict [s[i]] == false の間 length をデクリメントする
    • dict[s[i]] == true なら既出の文字列なので、その処理を行う
    • 文字数をカウントしている length のデクリメント
    • dict[s[j]] = false で既出の文字列と判定しないようにマーク外し

  5. i < len(s) の間、ステップ 2 - 4 を繰り返す

    func lengthOfLongestSubstring(s string) int {
dict := [128]bool{}
length, max := 0, 0
for i, j := 0, 0; i < len(s); i++ {
    index := s[i]
    if dict[index] {
        for ;dict[index]; j++ {
            length--
            dict[s[j]] = false
        }
    }
        
    dict[index] = true
    length++
    if length > max {
        max = length
    }
}
return max
}
  • for 文で複数のイテレーターを定義して使うという方法があるのか・・・！
    • for i, j := 0, 0; i < len(s); i++ {}
  • bool 配列をディクショナリとして使って、既出のパターンを検知するのも目からウロコ
    • Go 言語における bool のゼロ値は false なので、デフォルトで false が入っている
  • for loop はシンプルに回しつつも、カウントしたい値は for loop のスコープ外で定義しておき、複数のイテレーターを使って処理する

難しい！

See Also