2022/04/06

Leetcode Note: Go - Implement Strstr

Implement strStr() - LeetCode
https://leetcode.com/problems/implement-strstr/

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

所感

  • for loop を回し haystack に needle があるかチェックしていけば良さそう

実装準備

func strStr(haystack string, needle string) int {
    return 0
}

func main() {
    haystack := "hello"
    needle := "ll"
    
    fmt.Println(strStr(haystack, needle))
}

v1

func strStr(haystack string, needle string) int {
    output := -1

    for i := 0; i < len(haystack) - len(needle); i++ {
        if string(haystack[i:i+len(needle)]) == needle {
            return i
        }
    }

    return output
}

=> Wrong Answer

  • heystack = "a", needle = "a" の場合に 0 ではなく -1 を返してしまう
    • for loop の条件が悪い
    • どちらも 1文字 がインプットされるという、想定が出来てなかった

回答

func strStr(haystack string, needle string) int {
    output := -1

    for i := 0; i <= len(haystack) - len(needle); i++ {
        if string(haystack[i:i+len(needle)]) == needle {
            return i
        }
    }

    return output
}
  • シンプルなアルゴリズムだった
    • LeetCode が用意している Solution も無い
  • ループ回しつつ配列外へのアクセスを防ぐように、文字列チェックすれば OK
  • シンプルに値を return すれば良い関数であればデバッグも楽で試行錯誤もやりやすい

See Also