Implement strStr()
Description
For a given source string and a target string, you should output the first index(from 0) of target string in source string.
If target does not exist in source, just return -1
.Have you met this question in a real interview? Yes
Clarification
Do I need to implement KMP Algorithm in a real interview?
Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure you confirm with the interviewer first.
Example
If source = "source"
and target = "target"
, return -1
.
If source = "abcdabcdefg"
and target = "bcd"
, return 1
.
Challenge
O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)
这道题让我们在一个字符串中找另一个字符串第一次出现的位置,那我们首先要做一些判断,如果子字符串为空,则返回0,如果子字符串长度大于母字符串长度,则返回-1。然后我们开始遍历母字符串,我们并不需要遍历整个母字符串,而是遍历到剩下的长度和子字符串相等的位置即可,这样可以提高运算效率。然后对于每一个字符,我们都遍历一遍子字符串,一个一个字符的对应比较,
public class Solution {
/**
* @param source:
* @param target:
* @return: return the index
*/
public int strStr(String source, String target) {
// Write your code here
if(target == null || source == null) return -1;
if(target.length() == 0){
return 0;
}
if( source.length() < target.length()){
return -1;
}
for (int i = 0; i <= source.length() - target.length();i++ ){
int j = 0;
for(j = 0; j < target.length();j++ ){
if(target.charAt(j) != source.charAt(i+j)){
break;
}
}
if(j == target.length()){
return i;
}
}
return -1;
}
}
Last updated