LeetCodeに毎日挑戦してみた 28. Implement strStr()（Python、Go）

10022 ワード
leetcode Go Python Python テキストリンク

はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

10問目（問題28)

28. Implement strStr()

  • 問題内容

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

**

Example 1:

  Input: haystack = "hello", needle = "ll"
  Output: 2

Example 2:

  Input: haystack = "aaaaa", needle = "bba"
  Output: -1

Example 3:

  Input: haystack = "", needle = ""
  Output: 0

考え方

  1. haystack - needle回ループを回します　←　それ以上する必要がないため

  2. 一文字ごとに判定して違ったらその判定処理を抜けます

  3. needle の文字数と一致したらその時のindexを返します

  • 解答コード
def strStr(self, haystack, needle):
    if needle == "":
        return 0
    for i in range(len(haystack)-len(needle)+1):
        for j in range(len(needle)):
            if haystack[i+j] != needle[j]:
                break
            if j == len(needle)-1:
                return i
    return -1
  • Goでも書いてみます！
func strStr(haystack string, needle string) int {
    for i := 0; i < len(haystack)-len(needle)+1; i++ {
        j := 0
        for ; j < len(needle); j++ {
            if needle[j] != haystack[i+j] {
                break
            }
        }
        if j == len(needle) {
            return i
        }
    }
    return -1
}

別解

​ (1)

class Solution(object):
    def strStr(self, haystack, needle):        
        return haystack.find(needle)

findを使うとstrstr同様にその単語のindexを表示してくれます

(2)

class Solution(object):
def strStr(self, haystack, needle):
    for i in range(len(haystack) - len(needle)+1):
        if haystack[i:i+len(needle)] == needle:
            return i
    return -1

こちらは文字列の長さで比較しています。私は最初こちらを作成しました。

(3)

import "strings"

func strStr(haystack string, needle string) int {
    return strings.Index(haystack, needle)
}

goのfind版です

[セットトップ]springでjavaシステムのプロパティを設定する
pythonプログラム開発で、自分が直面した問題の一部(更新を続けます...)