【2022-08-06每日一题】1408. 数组中的字符串匹配
2022-08-06
2分钟阅读时长
2022-08-06每日一题：1408. 数组中的字符串匹配
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 words[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"] 输出：[]
提示：
1 <= words.length <= 1001 <= words[i].length <= 30words[i]仅包含小写英文字母。- 题目数据 保证 每个
words[i]都是独一无二的。
方法一：穷举， 暴力双层循环
func stringMatching(words []string) []string {
ans := []string{}
for i, wordi := range words {
for j, wordj := range words {
if i != j && strings.Contains(wordj, wordi) {
ans = append(ans, wordi)
break
}
}
}
return ans
}
方法二：拼字符串
func stringMatching(words []string) []string {
s, ans := strings.Join(words, "."), []string{}
for _, word := range words {
if strings.Index(s, word) != strings.LastIndex(s, word) {
ans = append(ans, word)
}
}
return ans
}
- 时间复杂度：O(n^2*L^2)
- 空间复杂度：O(1)
方法三：排序-遍历-内置函数
func stringMatching(words []string) []string {
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
ans := []string{}
for i := 0; i < len(words); i++ {
for j := i + 1; j < len(words); j++ {
if strings.Contains(words[j], words[i]) {
res = append(res, words[i])
break
}
}
}
return ans
}
Java kmp算法
class Solution {
public List<String> stringMatching(String[] words) {
List<String> list = new ArrayList();
int length = words.length;
for(int i=0;i<length;i++){
for(int j=0;j<length;j++){
if(words[i].length() >= words[j].length()) continue;
int[] ans = kmpNext(words[j]);
if(kmpSearch(words[j],words[i],ans)){
list.add(words[i]);
break;
}
}
}
return list;
}
// kmp查找
public boolean kmpSearch(String s1,String s2,int[] temp){
for(int i=0,j=0;i<s1.length();i++){
while(j > 0 && s1.charAt(i) != s2.charAt(j)){
j = temp[j-1];
}
if(s1.charAt(i) == s2.charAt(j)){
j++;
}
if(j == s2.length()) return true;
}
return false;
}
// kmp部分匹配表
public int[] kmpNext(String dest){
int len = dest.length();
int[] arr = new int[len];
arr[0] = 0;
for(int i=1,j=0;i<len;i++){
while( j > 0 && dest.charAt(i) != dest.charAt(j)){
j = arr[j-1];
}
if(dest.charAt(i) == dest.charAt(j)){
j++;
}
arr[i] = j;
}
return arr;
}
}
类似习题 820. 单词的压缩编码