LeetCode 524. 通过删除字母匹配到字典里最长单词

Categories:

题目描述
思路分析
1. 解法一：排序 + 双指针（推荐）
相似题目

题目描述

✅ 524. 通过删除字母匹配到字典里最长单词

思路分析

解法一：排序 + 双指针（推荐）

核心思路：

按长度降序、字典序升序排序字典。

依次判断每个单词是否为原串的子序列。

首个满足条件的即为答案。

复杂度分析：

时间复杂度：O(M * L)，其中 M 为字典单词数，L 为平均长度。

空间复杂度：O(1)，仅使用常数额外空间。

import java.util.Collections;
import java.util.List;

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, (a, b) -> {
            if (a.length() != b.length()) {
                return b.length() - a.length();
            }
            return a.compareTo(b);
        });

        for (String word : dictionary) {
            if (isSubsequence(s, word)) {
                return word;
            }
        }

        return "";
    }

    private boolean isSubsequence(String s, String t) {
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == t.length();
    }
}

import "sort"

func findLongestWord(s string, dictionary []string) string {
	sort.Slice(dictionary, func(i, j int) bool {
		if len(dictionary[i]) != len(dictionary[j]) {
			return len(dictionary[i]) > len(dictionary[j])
		}
		return dictionary[i] < dictionary[j]
	})

	for _, word := range dictionary {
		if isSubsequence(s, word) {
			return word
		}
	}

	return ""
}

func isSubsequence(s string, t string) bool {
	i, j := 0, 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			j++
		}
		i++
	}
	return j == len(t)
}

相似题目

题目	难度	考察点
392. 判断子序列	简单	双指针
522. 最长特殊序列 II	中等	子序列
720. 词典中最长的单词	简单	字符串
1048. 最长字符串链	中等	动态规划
340. 至多包含 K 个不同字符的最长子串	困难	双指针

本文作者: HGNULB

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