LeetCode 1408. 数组中的字符串匹配

Categories:

题目描述
思路分析
1. 解法一：按长度排序 + 子串判断（推荐）
相似题目

题目描述

✅ 1408. 数组中的字符串匹配

思路分析

解法一：按长度排序 + 子串判断（推荐）

核心思路：

按字符串长度升序排序。

对每个字符串，只需检查是否为任一更长字符串的子串。

若是子串则加入结果。

复杂度分析：

时间复杂度：O(n^2 * L)，其中 L 为平均长度。

空间复杂度：O(n)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    public List<String> stringMatching(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        List<String> res = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (words[j].contains(words[i])) {
                    res.add(words[i]);
                    break;
                }
            }
        }
        return res;
    }
}

import "sort"

func stringMatching(words []string) []string {
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })

    res := make([]string, 0)
    for i := 0; i < len(words); i++ {
        for j := i + 1; j < len(words); j++ {
            if contains(words[j], words[i]) {
                res = append(res, words[i])
                break
            }
        }
    }
    return res
}

func contains(s string, sub string) bool {
    return len(sub) <= len(s) && (len(sub) == 0 || indexOf(s, sub) >= 0)
}

func indexOf(s string, sub string) int {
    for i := 0; i+len(sub) <= len(s); i++ {
        if s[i:i+len(sub)] == sub {
            return i
        }
    }
    return -1
}

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	字符串匹配
459. 重复的子字符串	简单	字符串
686. 重复叠加字符串匹配	中等	字符串
392. 判断子序列	简单	双指针
1268. 搜索推荐系统	中等	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/76873397