Loading...
首页 计算机 算法 算法题 简单

实现 strStr () 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

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

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

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

提示：

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

题解一

/**
 * 思路：
 * 将 needle 的第一个字符与 haystack 的每个字符匹配，
 * 如果匹配成功就截取当前字符到跟 needle 的一样长度，
 * 如果两者相等则返回当前下标，直到最后都没匹配成功返回 - 1
 *
 */
public class Soultion {
    public int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) return -1;
        int length = needle.length();
        char first = needle.charAt(0);
        for (int i = 0; i <= haystack.length() - length; i++){
            if (haystack.charAt(i) == first){
                String substring = haystack.substring(i, i + length);
                if (substring.equals(needle)){
                    return i;
                }
            }
        }
        return -1;
    }
}
题解二
/**
 * 最简单的办法
 * 挨着一个一个匹配
 */
public class Soultion {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i <= haystack.length() - needle.length(); i++){
            boolean flag = true;
            for (int j = 0; j < needle.length(); j++){
                if (haystack.charAt(i + j) != needle.charAt(j)){
                    flag = false;
                }
            }
            if (flag) return i;
        }
        return -1;
    }
}
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-strstr