LeetCode日本語修行7日目- [28- strStr()の実現]
Implement strStr()
参考:https://leetcode.com/problems/implement-strstr/
問題の内容:
haystackの中にneedleが最初に現れるIndexを返し、ないの場合は-1を返します。
明確にします。
ちなみに、needleが空の文字列の場合、何を返すべきでしょうか?
例:
例1:
Input: haystack = "hello", needle = "ll"
Output: 2
例2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
例3:
Input: haystack = "", needle = ""
Output: 0
ヒント:
0 <= haystack.length, needle.length <= 5 * 104
haystack and needle consist of only lower-case English characters.
この問題の解答は、普通のForLoopでできます、
又はKMP法を使って、回答します。
KMP法の中に、一番理解難しいのは、多分PartialMatchTableの事です、
PartialMatchTableとは、指定のStringの中に、prefixとsuffix イコールの部分です。
abcdab
の場合
a -> 0
ab -> [prefix: a ,suffix: b] ->0
abc ->[prefix: a,ab ,suffix: c,bc] ->0
abcd ->[prefix: a,ab,abc ,suffix: d,dc,dcb] ->0
abcda ->[prefix: a,ab,abc,abcd ,suffix: a,ad,adc,adcb] -> aは両方の中に共に出ました、 1です
abcdab ->[prefix: a,ab,abc,abcd,abcda ,suffix: b,ba,bad,badc,badcb] ->0
この場合:
abcdab
のPartialMatchTableは
000010
です
class Solution {
fun strStr(haystack: String, needle: String): Int {
var m = needle.length
var n = haystack.length
if(m == 0){
return 0
}
val pi = IntArray(m)
var j = 0
for(i in 1 until m){
while(j > 0 && needle[j] != needle[i]){
j = pi[j-1]!!
}
if(needle[i] == needle[j]){
j++
}
pi[i] = j
}
var jj = 0
for(i in 0 until n){
while(jj > 0 && haystack[i] != needle[jj]){
jj = pi[jj-1]!!
}
if(haystack[i] == needle[jj]){
jj++
}
if(jj == m){
return i - m + 1
}
}
return -1
}
}
Author And Source
この問題について(LeetCode日本語修行7日目- [28- strStr()の実現]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/b374e637f5e5a5e10249著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .