2

Leetcode 028 实现 strStr() ( Implement strStr() ) 题解分析

 2 years ago
source link: https://nicksxs.me/2021/10/31/Leetcode-028-%E5%AE%9E%E7%8E%B0-strStr-Implement-strStr-%E9%A2%98%E8%A7%A3%E5%88%86%E6%9E%90/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Leetcode 028 实现 strStr() ( Implement strStr() ) 题解分析

发表于 2021-10-31 分类于 Java ， leetcode 阅读次数： 3 Disqus： 0 Comments

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

Input: haystack = "", needle = ""
Output: 0

字符串比较其实是写代码里永恒的主题，底层的编译器等处理肯定需要字符串对比，像 kmp 算法也是很厉害

public int strStr(String haystack, String needle) {
        // 如果两个字符串都为空，返回 -1
        if (haystack == null || needle == null) {
            return -1;
        }
        // 如果 haystack 长度小于 needle 长度，返回 -1
        if (haystack.length() < needle.length()) {
            return -1;
        }
        // 如果 needle 为空字符串，返回 0
        if (needle.equals("")) {
            return 0;
        }
        // 如果两者相等，返回 0
        if (haystack.equals(needle)) {
            return 0;
        }
        int needleLength = needle.length();
        int haystackLength = haystack.length();
        for (int i = needleLength - 1; i <= haystackLength - 1; i++) {
            // 比较 needle 最后一个字符，倒着比较稍微节省点时间
            if (needle.charAt(needleLength - 1) == haystack.charAt(i)) {
                // 如果needle 是 1 的话直接可以返回 i 作为位置了
                if (needle.length() == 1) {
                    return i;
                }
                boolean flag = true;
                // 原来比的是 needle 的最后一个位置，然后这边从倒数第二个位置开始
                int j = needle.length() - 2;
                for (; j >= 0; j--) {
                    // 这里的 i- (needleLength - j) + 1 ) 比较绕，其实是外循环的 i 表示当前 i 位置的字符跟 needle 最后一个字符
                    // 相同，j 在上面的循环中--，对应的 haystack 也要在 i 这个位置 -- ，对应的位置就是 i - (needleLength - j) + 1
                    if (needle.charAt(j) != haystack.charAt(i - (needleLength - j) + 1)) {
                        flag = false;
                        break;
                    }
                }
                // 循环完了之后，如果 flag 为 true 说明 从 i 开始倒着对比都相同，但是这里需要起始位置，就需要
                // i - needleLength + 1
                if (flag) {
                    return i - needleLength + 1;
                }
            }
        }
        // 这里表示未找到
        return  -1;
    }

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK