【LeetCode】数组中的字符串匹配 Java 题解

作者：Albert

2022 年 8 月 06 日
本文字数：1053 字
阅读完需：约 3 分钟

题目描述

给你一个字符串数组 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"]输出：[]
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/string-matching-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串数组匹配题目，题目稍微有些繁琐，简单理解就是求字符串 words[i]的子串的个数。
分析题目，求子串，我们可以明显得到长度短的字符串可能是长度长的字符串的子串。根据这个结论，我们使用数组排序，按照字符串的长度进行升序排序。在代码实践中，就是重载 Comparator，实现自定义的排序操作。
对于排序完成的字符串数组，我们可以使用排序的方式，先从尾部取出 words[i]，在从头部开始，依次取出 words[j], 判断 words[j] 是不是 words[i]的子串即可。
这里需要注意的是，在返回的结果中，words 字符串不能重复，需要注意一下去重。具体实现代码如下，供参考。

通过代码

class Solution {    public List<String> stringMatching(String[] words) {        List<String> ans = new ArrayList<>();        int n = words.length;        Arrays.sort(words, new Comparator<String>() {            @Override            public int compare(String o1, String o2) {                return o1.length() - o2.length();            }        });
        for (int i = n - 1; i > 0; i--) {            for (int j = 0; j < i; j++) {                if (words[i].indexOf(words[j]) != -1) {                    if (ans.contains(words[j])) {                        continue;                    }                    ans.add(words[j]);                }            }        }
        return ans;    }}