LeetCode 面试题 17.15. 最长单词

Categories:

题目描述
思路分析
1. 解法一：排序 + 单词拆分 DP（推荐）
相似题目

题目描述

✅ 面试题 17.15. 最长单词

思路分析

解法一：排序 + 单词拆分 DP（推荐）

核心思路：

将单词按长度升序排序，保证拆分时只用更短单词。

用集合保存已处理的单词，对当前单词做单词拆分 DP。

若可拆分且长度更长（或同长字典序更小），更新答案。

复杂度分析：

时间复杂度：O(L^2)，其中 L 为所有单词长度之和的上界。

空间复杂度：O(L)，用于 DP 数组与集合存储。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());

        Set<String> dict = new HashSet<>();
        String best = "";

        for (String word : words) {
            if (wordBreak(word, dict)) {
                if (word.length() > best.length()
                        || (word.length() == best.length() && word.compareTo(best) < 0)) {
                    best = word;
                }
            }
            dict.add(word);
        }

        return best;
    }

    private boolean wordBreak(String word, Set<String> dict) {
        if (dict.isEmpty()) {
            return false;
        }

        int n = word.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (!dp[j]) {
                    continue;
                }
                if (dict.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}

import "sort"

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

	dict := make(map[string]struct{})
	best := ""

	for _, word := range words {
		if canBreak(word, dict) {
			if len(word) > len(best) || (len(word) == len(best) && word < best) {
				best = word
			}
		}
		dict[word] = struct{}{}
	}

	return best
}

func canBreak(word string, dict map[string]struct{}) bool {
	if len(dict) == 0 {
		return false
	}

	n := len(word)
	dp := make([]bool, n+1)
	dp[0] = true

	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			if !dp[j] {
				continue
			}
			if _, ok := dict[word[j:i]]; ok {
				dp[i] = true
				break
			}
		}
	}

	return dp[n]
}

相似题目

题目	难度	考察点
139. 单词拆分	中等	动态规划
140. 单词拆分 II	困难	回溯
472. 连接词	困难	单词拆分
720. 词典中最长的单词	简单	前缀判断
1048. 最长字符串链	中等	动态规划

本文作者: HGNULB

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