strStr

Question

  1. strstr (a.k.a find sub string), is a useful function in string operation.
  2. You task is to implement this function.
  4. For a given source string and a target string,
  5. you should output the "first" index(from 0) of target string in source string.
  7. If target is not exist in source, just return -1.
  9. Example
  10. If source="source" and target="target", return -1.
  12. If source="abcdabcdefg" and target="bcd", return 1.
  14. Challenge
  15. O(n) time.
  17. Clarification
  18. Do I need to implement KMP Algorithm in an interview?
  20.     - Not necessary. When this problem occurs in an interview,
  21.     the interviewer just want to test your basic implementation ability.

題解

對於字串查找問題，可使用雙重for迴圈解決，效率更高的則為KMP算法。

Java

  1. /**
  2.  * http://www.jiuzhang.com//solutions/implement-strstr
  3.  */
  4. class Solution {
  5.     /**
  6.      * Returns a index to the first occurrence of target in source,
  7.      * or -1  if target is not part of source.
  8.      * @param source string to be scanned.
  9.      * @param target string containing the sequence of characters to match.
  10.      */
  11.     public int strStr(String source, String target) {
  12.         if (source == null || target == null) {
  13.             return -1;
  14.         }
  16.         int i, j;
  17.         for (i = 0; i < source.length() - target.length() + 1; i++) {
  18.             for (j = 0; j < target.length(); j++) {
  19.                 if (source.charAt(i + j) != target.charAt(j)) {
  20.                     break;
  21.                 } //if
  22.             } //for j
  23.             if (j == target.length()) {
  24.                 return i;
  25.             }
  26.         } //for i
  28.         // did not find the target
  29.         return -1;
  30.     }
  31. }

源碼分析

  1. 邊界檢查：source和target有可能是空串。
  2. 邊界檢查之下標溢出：注意變量i的循環判斷條件，如果是單純的i < source.length()則在後面的source.charAt(i + j)時有可能溢出。
  3. 代碼風格：（1）運算符==兩邊應加空格；（2）變量名不要起s1``s2這類，要有意義，如target``source；（3）即使if語句中只有一句話也要加大括號，即{return -1;}；（4）Java 代碼的大括號一般在同一行右邊，C++ 代碼的大括號一般另起一行；（5）int i, j;聲明前有一行空格，是好的代碼風格。
  4. 不要在for的條件中聲明i,j，容易在循環外再使用時造成編譯錯誤，錯誤代碼示例：

Another Similar Question

  1. /**
  2.  * http://www.jiuzhang.com//solutions/implement-strstr
  3.  */
  4. public class Solution {
  5.     public String strStr(String haystack, String needle) {
  6.         if(haystack == null || needle == null) {
  7.             return null;
  8.         }
  9.         int i, j;
  10.         for(i = 0; i < haystack.length() - needle.length() + 1; i++) {
  11.             for(j = 0; j < needle.length(); j++) {
  12.                 if(haystack.charAt(i + j) != needle.charAt(j)) {
  13.                     break;
  14.                 }
  15.             }
  16.             if(j == needle.length()) {
  17.                 return haystack.substring(i);
  18.             }
  19.         }
  20.         return null;
  21.     }
  22. }