LintCode 13. strStr 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/strstr/
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.
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 your confirm with the interviewer first.
Example
If source = "source" and target = "target", return -1.
If source = "abcdabcdefg" and target = "bcd", return 1.
解题思路
题目是求字符串target在字符串source中出现的位置。
- 先检查输入的合理性，source、target是否为空，为空则返回-1。
- 二重循环，比较source每个位置开始能否完整地走完target的每一个字符。
参考代码
class Solution {
/**
* Returns a index to the first occurrence of target in source,
* or -1 if target is not part of source.
* @param source string to be scanned.
* @param target string containing the sequence of characters to match.
*/
public int strStr(String source, String target) {
if (source == null || target == null) {
return -1;
}
for (int i = 0; i < source.length() - target.length() + 1; i++) {
int j;
for (j = 0; j < target.length(); j++) {
if (source.charAt(i + j) != target.charAt(j)) {
break;
}
}
if (j == target.length()) {
return i;
}
}
return -1;
}
}