Leetcode - Implement strStr()

图片 1Paste_Image.png

My code:

My code:

public class Solution { public String shortestPalindrome { if (s == null || s.length { return s; } String t = s + "#" + new StringBuilder.reverse().toString(); int[] dp = new int[t.length() + 1]; int j = 0; int k = -1; dp[0] = -1; while (j < dp.length - 1) { if (k == -1 || t.charAt == t.charAt { k++; j++; dp[j] = k; } else { k = dp[k]; } } StringBuilder sb = new StringBuilder(s.substring(dp[dp.length - 1])); return sb.reverse().toString() + s; } public static void main(String[] args) { Solution test = new Solution(); String ret = test.shortestPalindrome("ababbbabbaba"); System.out.println; }}
public class Solution { public int strStr(String haystack, String needle) { if (haystack == null || needle == null) return -1; if (needle.length return 0; int[] next = getNext; int j = 0; int i = 0; while (i < haystack.length() && j < needle.length { if (j == -1 || haystack.charAt == needle.charAt { i++; j++; } else j = next[j]; } if (j == needle.length return i - j; else return -1; } private int[] getNext(String needle) { int[] next = new int[needle.length()]; int k = -1; int j = 0; next[0] = -1; while (j < needle.length { if (k == -1 || needle.charAt == needle.charAt { k++; j++; if (needle.charAt != needle.charAt next[j] = k; else next[j] = next[k]; } else k = next[k]; } return next; } public static void main (String[] args) { Solution test = new Solution(); System.out.println(test.strStr("mississippi", "a")); }}

reference:

My test result:

这道题目搞了很久。终于看了答案自己写了出来。首先做了下 implement strStr() 题,复习了下 KMP算法终于记起来怎么写了,希望下次不要忘记。。。

图片 2

然后这道题目,可以继续抽象。找到 以 index = 0 开头的substring,是最长的palindrome找到之后,将剩余的部分反转,加在前面,就行了。

这道题目要求是用KMP算法来做的。具体KMP算法是什么东西,就看这篇博客吧。讲的太详细了。

下面的问题是,如果找到这个最长的palindrome.

KMP 算法的核心,或者是难点,就是构造next[] 数组。一旦next[] 数组构造好了,主程序很好写。那么, next[] 数组的难点是什么。关键在于理解。next[j] 是什么意义呢?意义是, 在 [0, j - 1] 这个区域内,string needle 的最大前缀后缀相等长度。也就是说, next[] 数组求解过程中,是通过 next[j - 1] 来求 next[j], 当等于j时,此时要求的又是 next[j + 1]了。所以, j < needle.length()

brute-force: O TLE但是仍然佩服,能够走到这一步的人。这是思维的力量。即使没做出来,这道题目的意义,已经达到了。

  • 1因为当j = needle.length() - 2 时, 就可以求出 next[needle.length() - 1] 了。

如何在 O 找到他呢?构造一个 string:s + "#" + reverse为什么需要这个 #强行隔开两个string

然后还需要理解一些概念。next[j] = 0; 是什么含义。代表在 [0, j - 1] 这段区域内,string needle 没有重复的前缀后缀,随意,直接拿 haystack[i] 与 needle[0] 进行比较了。相当于,在 i 处失配时,直接将字符串needle头部直接移动到i处。重新进行匹配。

如果 [0, k] match [j, j + k]k >= s.length() && j < s.length()之后将这个字符串取出来。s.substring 就会越界。因为 s 的指针都跑到reverse 去找匹配了,并且还找到了,导致长度比实际长度还要长。所以我们需要用 # 强行隔开两者。

那么 next[j] = -1 是什么含义呢?代表, haystack[i] 也不等于 needle[0], 即,在i处失配时,甚至都不需要将needle头部与i开始的字符串重新进行匹配了,直接跳过i,和i

其次,利用KMP 构造 next 数组。这里,有两个注意点:1 . dp length 应该等于 s.length + 1也就是多一位,用来衡量 [0, len - 1] 的情况。和KMP略有不同2 . 我们只关注dp最后一位的情况。因为它包含的是,s 以0开头,最长的panlindrome 的长度。

  • 1处开始的字符串进行重新匹配。这就是改进版的KMP,将next[] 优化了。

| ------> | # | <------ |012345 543210所以如果 dp[len - 1] = 2表示,有两位 prefix match with postfix即, s[0, 1] 是最长回文字符串。然后我们拿到这个长度,把之后的string拿出来reverse,加在前面。这道题目就解决了。

而且求 next[] 数组时,

差不多就这样了。

while (j < needle.length { if (k == -1 || needle.charAt == needle.charAt { k++; j++; if (needle.charAt != needle.charAt next[j] = k; else next[j] = next[k]; } else k = next[k]; }

KMP 文章:

一开始我在想,在needle和haystack匹配到很长时,如果此时失配,那么k = next[k],这时再次失配呢?没关系,那么就再次进行循环。因为在这个过程中,j是不变化的,k是不断往后倒退的。直到找到符合的情况。这就是一种递归啊。用while体现出来的一种递归思想,更科学的应该称为,迭代?

Anyway, Good luck, Richardo! -- 09/20/2016

还有就是优化next的代码,多了这么一段。

if (needle.charAt != needle.charAt next[j] = k;else next[j] = next[k];

我在想,在needle和haystack匹配到很长时,如果此时下一个继续匹配了,但是检测出,needle.charAt == needle.charAt那么我们需要执行这个操作,next[j] = next[k];那我们一定可以保证,needle.charAt != needle.charAt 吗?一定可以保证的。因为我们是从0 开始 往后填充next[]的,我们一步步往前走,保证每一步的needle.charAt != needle.charAt所以一直递归到后面,是可以保证的。很像是那个 科学证明法,从1开始证明,到后面,都理所当然了。

KMP就总结到这里了。

**总结: String, KMP**

Anyway, Good luck, Richardo!

My code:

public class Solution { public int strStr(String haystack, String needle) { String s = haystack; String p = needle; if (s == null || p == null) { return -1; } else if (p.length { return 0; } int[] next = getNext; int i = 0; int j = 0; while (i < s.length() && j < p.length { if (s.charAt == p.charAt { i++; j++; } else { if  { i++; } else { j = next[j]; } } } if (j >= p.length { return i - p.length(); } else { return -1; } } private int[] getNext { int[] dp = new int[p.length()]; dp[0] = -1; int k = -1; int j = 0; while (j < dp.length - 1) { if (k == -1 || p.charAt == p.charAt { k++; j++; dp[j] = k; } else { k = dp[k]; } } return dp; }}

又把 KMP算法看了一遍,希望这次别再忘了。其实就是 DP

Anyway, Good luck, Richardo! -- 09/20/2016

本文由365bet体育在线官网发布于网络编程,转载请注明出处:Leetcode - Implement strStr()

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。