對于一個(gè)給定的 source 字符串和一個(gè) target 字符串链瓦，你應(yīng)該在 source 字符串中找出 target 字符串出現(xiàn)的第一個(gè)位置(從0開始)。如果不存在盯桦，則返回 -1慈俯。
說明：在面試中我是否需要實(shí)現(xiàn)KMP算法？
- 不需要俺附，當(dāng)這種問題出現(xiàn)在面試中時(shí)肥卡，面試官很可能只是想要測試一下你的基礎(chǔ)應(yīng)用能力。當(dāng)然你需要先跟面試官確認(rèn)清楚要怎么實(shí)現(xiàn)這個(gè)題事镣。
- 樣例
如果 source = "source" 和 target = "target"步鉴，返回 -1揪胃。
如果 source = "abcdabcdefg" 和 target = "bcd"，返回 1氛琢。
O(n2)的算法是可以接受的喊递。如果你能用O(n)的算法做出來那更加好。（提示：KMP）
public class strStr {
/**
* 解決思路：首先我們有source字符串和target字符串阳似，source字符串最后的幾個(gè)字符串長度小于target肯定不會(huì)有首次出現(xiàn)的可能骚勘。
* 所以應(yīng)該進(jìn)行遍歷操作的source字符串的長度是（source.length-target.length）的長度。
* 在上面那個(gè)遍歷中撮奏，我們可以獲取source的position獲取具體字符俏讹，再將target的所有字符串進(jìn)行遍歷，如果第一個(gè)字符與source的相同
* 那么
* 畜吊，繼續(xù)下一個(gè)target及下一個(gè)source中的字符進(jìn)行對比泽疆，直到target.length次后如果完全想同則返回外層遍歷那個(gè)position，
* 如果不同則返回上層遍歷玲献，postion+1殉疼，繼續(xù)進(jìn)行target的比對操作，如果全部沒有則返回-1捌年；
* 時(shí)間復(fù)雜度為：O(n^2)
*/
public int solution(String source, String target) {
if (source == null || target == null) {
return -1;
}
for (int i = 0; i <= source.length() - target.length(); i++) {
int j = 0;
for (j = 0; j < target.length(); j++) {
if (source.charAt(i + j) != target.charAt(j))
break;
}
if (j == target.length()) {
return i;
}
}
return -1;
}
}
