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; } }