呃呃，今天被LeetCode中的一道题搞得挺头大的，我翻译了一下还挺有意思的，也就是大海捞针，乍一看觉着这道题贼简单，实质上就是让你实现一个类似于Java中indexOf()这样的一个函数，搞不懂这道题AC的人为什么只有百分之二十多呢么少，但当自己试图去实现题目要求时才发现这道题没有想象中呢么简单啊，真真硬是磨了一个半小时才AC掉，还是很菜额自己，下面是题目与相关测试用例……
Implement
strStr()
.
Return the index of the first occurrence of needle in haystack, or
-1
if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
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()
.
开始自己想的是能否在O(n)时间内实现题目要求，但因为种种原因发现并不能，并不是所有算法都可以优化到O(n)时间内的，所以最终环视采取了暴力的方法，我的想法是将haystack中的每个字母分别与needle中的首字母进行比较，如果相同则进入内循环，内循环中比较haystack后续字母与needle的后续字母是否完全相等，如果不相等则将计数器count重置为0，最后判断至haystack末尾是否有count等于needle的长度进而返回该循环的其实索引，也就是第一次给定字符串出现的位置，如果不存在则返回-1。这道题可能难点就是测试用例了，确实很难一次性想的呢么完整，如果想要快速的解决这个问题，这就要求我们平时养成一个良好的编程习惯，从而能以全面的思维去解决问题。下面是我的Java AC：
package com.gaoxue.LeetCode;
public class ImplementIndexOf {
/**
* 磨了一个多小时终于通过了所有测试用例，哇、真的恐怖呃呃
* @param haystack
* @param needle
* @return
*/
public int strStr(String haystack, String needle) {
if(needle.length()==0)
return 0;
if(needle.length()>haystack.length())
return -1;
int count = 0,index;
for(int i=0;i<haystack.length();i++){
if(haystack.charAt(i)==needle.charAt(0)) {
if(needle.length()==1)
return 0;
if(i+needle.length()>haystack.length())
return -1;
index = i+1;
for(int j=1;j<needle.length();j++) {
if(haystack.charAt(index++)==needle.charAt(j))
count++;
else {
count = 0;
break;
}
if(count==needle.length()-1)
return i;
}
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(new ImplementIndexOf().strStr("mississippi", "issippi"));
/*String s = "abc";
System.out.println(s.indexOf('a'));
System.out.println(s.indexOf("bc"));*/
}
}
同样有着O(n^2)的暴力，然代码实现确实这样的~
public int strStr2(String haystack, String needle) {
for (int i = 0;; i++) {
for (int j = 0;; j++) {
if (j == needle.length())
return i;
if (i + j == haystack.length())
return -1;
if (needle.charAt(j) != haystack.charAt(i + j))
break;
}
}
}
已经很简单了吧，然最最genius的解决办法还是下面的实现，惊呆了~
public int strStr3(String haystack, String needle) {
return haystack.indexOf(needle);
}
你信么，短短的一行代码是可以AC的，我信是因为我试过了哈哈，欲哭无泪、自己好笨啊~ 不过勤能补拙，虽然第三种方法是可以AC的，但我们平时练习的时候其实是应该自己手动实现的，这样对我们的编程能力会有很大的帮助，当然如果在面试中遇到此类问题，肯定是要寻求最快的方法的，这样不仅可以给其他题目分配充足的时间，更重要的是聪明的解题方法也会给面试官留下深刻的印象，在面试过程会加分很多。那么还是过去曾说过的话，我们在解决问题时不能把视野思维局限在题目本身，这样亦会有聪明的解题方法源于你自己啦~