Easy

题目描述

给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。

示例 1：

输入：words = ["mass","as","hero","superhero"]
输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。

示例 2：

输入：words = ["leetcode","et","code"]
输出：["et","code"]
解释："et" 和 "code" 都是 "leetcode" 的子字符串。

示例 3：

输入：words = ["blue","green","bu"]
输出：[]
解释：words 中的字符串都不是其他任何字符串的子字符串。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] 仅含小写英文字母。
  • 题目数据 保证 每个 words[i] 都是独一无二的。

解题思路

这道题要求找出数组中作为其他单词子串的所有单词。

思路分析：

最直观的暴力解法是对每个单词，检查它是否是数组中其他单词的子串。具体步骤：

  1. 遍历数组中的每个单词作为候选子串
  2. 对于每个候选子串，遍历数组中的其他单词，检查该候选是否为其子串
  3. 如果找到包含关系，将候选子串加入结果

优化思路：

  • 可以先按字符串长度排序，短的字符串更可能是长字符串的子串
  • 使用内置的字符串查找函数（如 find、indexOf、contains 等）来判断子串关系
  • 对于更高级的字符串匹配，可以使用 KMP 算法，但在此题的数据规模下，暴力解法已经足够高效

推荐解法： 使用暴力遍历 + 内置字符串查找函数，代码简洁且性能满足要求。

时间复杂度主要取决于字符串比较，在给定的数据范围内表现良好。

代码实现

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        vector<string> result;
        int n = words.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && words[j].find(words[i]) != string::npos) {
                    result.push_back(words[i]);
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        result = []
        
        for i in range(len(words)):
            for j in range(len(words)):
                if i != j and words[i] in words[j]:
                    result.append(words[i])
                    break
        
        return result

public class Solution {
    public IList<string> StringMatching(string[] words) {
        IList<string> result = new List<string>();
        
        for (int i = 0; i < words.Length; i++) {
            for (int j = 0; j < words.Length; j++) {
                if (i != j && words[j].Contains(words[i])) {
                    result.Add(words[i]);
                    break;
                }
            }
        }
        
        return result;
    }
}

var stringMatching = function(words) {
    const result = [];
    
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i !== j && words[j].includes(words[i])) {
                result.push(words[i]);
                break;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² × m)n 为数组长度，m 为字符串平均长度，需要两层循环比较字符串
空间复杂度O(k × m)k 为结果数组长度，m 为字符串平均长度

相关题目