实现strStr()从繁到简 -LeetCode

淡淡的烟草味﹌ 2022-05-19 02:18 166阅读 0赞

### 题目： ###

实现 [strStr()][strStr] 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 **-1**。

**示例1：**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td> <p>输入：haystack = "hello", needle = "ll"</p> <p>输出：2</p> </td> 
  </tr> 
 </tbody> 
</table>

**示例2：**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td> <p>输入：haystack = "aaaaa", needle = "bba"</p> <p>输出：-1</p> </td> 
  </tr> 
 </tbody> 
</table>

**说明：**

当 `needle` 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 `needle` 是空字符串时我们应当返回 0 。这与C语言的 [strstr()][strStr] 以及 Java的 [indexOf()][indexOf] 定义相符。

### 解答（java）： ###

**方法一：**

最复杂，先找到第一个 haystack 中字符与 needle 匹配的位置；再逐一判断之后的每个字符的是否一致。

class Solution {
        public int strStr(String haystack, String needle) {
            if(needle.length() == 0){
                return 0;
            }
            int i = 0;
            while(i < haystack.length()){
                if(haystack.charAt(i) != needle.charAt(0)){
                    i++;
                    continue;
                }
                if(haystack.charAt(i) == needle.charAt(0)){
                    if(haystack.length()-i >= needle.length()){
                        int j;
                        for(j = 0; j < needle.length(); j++){
                            if(haystack.charAt(i+j) != needle.charAt(j)){
                                break;
                            }
                        }
                        if(j == needle.length()){
                            return i;
                        }
                    }
                } 
                i++;
            }
            return -1;
        }
    }

**方法二：**

与方法一差别的地方是找到第一个匹配的字符串后，从 haystack 中截取与 needle 长度相等的子字符串，利用字符串的 equals() 方法判断是否匹配。

class Solution {
        public int strStr(String haystack, String needle) {
            if("".equals(needle)){
                return 0;
            }
            int lenNeedle = needle.length();
            int lenHaystack = haystack.length();
            int i = 0;
            while(i < lenHaystack){
                if(haystack.charAt(i) == needle.charAt(0)){
                    if(lenHaystack-i >= lenNeedle){
                        String temp = haystack.substring(i,i+lenNeedle);
                        if(temp.equals(needle)){
                            return i;
                        }
                    }
                }
                i++;
            }
            return -1;
        }
    }

方法三：

直接利用字符串的 indexOf() 方法匹配子字符串。

class Solution {
        public int strStr(String haystack, String needle) {
            return haystack.indexOf(needle);
        }
    }

解题的过程也是在不断的改进的过程，当我们通过大量的算法设计和实现，思维的能力也会随之增强。

但是有些时候还是要先获取编程语言本身提供的函数，这不仅会提高效率，也会对之后的工作有所帮助。

这并不意味着我们前面思考的过程是无用的，函数库也是需要实现的，并不是所有的函数本来就有。

[strStr]: https://baike.baidu.com/item/strstr/811469
[indexOf]: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf%28java.lang.String%29