LC 1967.Number of Strings That Appear as Substrings in Word

题目描述

这是 LeetCode 上的 1967. 作为子字符串出现在单词中的字符串数目 - 力扣（LeetCode） ，难度为简单。

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：patterns = ["a","abc","bc","d"], word = "abc"
输出：3
解释：
- "a" 是 "abc" 的子字符串。
- "abc" 是 "abc" 的子字符串。
- "bc" 是 "abc" 的子字符串。
- "d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

输入：patterns = ["a","b","c"], word = "aaaaabbbbb"
输出：2
解释：
- "a" 是 "aaaaabbbbb" 的子字符串。
- "b" 是 "aaaaabbbbb" 的子字符串。
- "c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

输入：patterns = ["a","a","a"], word = "ab"
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word "ab" 中。

提示：

• 1 <= patterns.length <= 100
• 1 <= patterns[i].length <= 100
• 1 <= word.length <= 100
• patterns[i] 和 word 由小写英文字母组成

解答

方法一：暴力解法

根据题目要求进行模拟即可。

class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int cnt = 0;
        for (String s : patterns) {
            if (isSubString(s, word)) {
                ++cnt;
            }
        }
        return cnt;
    }

    public static boolean isSubString(String sub, String word) {
        if (sub.length() > word.length()) {
            return false;
        }
        for (int i = 0; i + sub.length() <= word.length(); ++i) {
            boolean f = true;
            for (int j = 0; j < sub.length(); ++j) {
                if (sub.charAt(j) != word.charAt(j + i)) {
                    f = false;
                    break;
                }
            }
            if (f) {
                return f;
            }
        }
        return false;
    }
}

• 时间复杂度：\(O(n \times \sum_im_i)\)，其中 n 为字符串 word 的长度， \(m_i\) 为字符串 patterns[i] 的长度。对于 patterns 中的每个字符串 patterns[i] ，暴力匹配判断是否为 word 子串的时间复杂度为 \(O(n \times m_i)\)。

• 空间复杂度：\(O(1)\)。

每题一图