LeetCode 139.单词拆分Java回溯解法超时原因及优化方案

题目信息 #

题目链接：139. Word Break

问题描述 #

现有纯回溯解法无法通过全部测试用例，触发超时。需求为保留回溯思路求解本题，需要定位现有代码的问题，在已知原解法时间复杂度为O(2^n + n²)的前提下，给出优化方案以通过全部测试用例。

原始超时代码 #

class Solution {
    boolean found;
    public boolean wordBreak(String s, List<String> wordDict) {
        backtrack(s, wordDict, 0);
        return found;
    }
    public void backtrack(String s, List<String> wordDict, int index){
        if(found == true) return;
        if(index == s.length()){
            found = true;
            return;
        }
        for(int len = 1; index + len <= s.length(); len++){
            String prefix = s.substring(index, index + len);
            if(wordDict.contains(prefix)){
                backtrack(s, wordDict, index + len);
            }
        }
    }
}

原始代码存在的问题 #

• 无状态缓存导致大量重复计算：同一索引位置index会被多条不同路径重复访问，每次访问都会重新遍历所有可能的前缀长度做匹配，重复执行"验证从index出发能否到达字符串末尾"的逻辑，这部分冗余计算是超时的核心原因。
• 词典查询效率低：使用List结构存储词典，contains方法时间复杂度为O(k)（k为词典单词总数），每次前缀匹配都需要遍历整个词典，额外增加耗时。
• 无长度剪枝：循环中前缀长度从1一直遍历到字符串末尾，若词典中最长单词长度远小于剩余字符串长度，超出最长单词长度的前缀判断完全是无效操作。

优化方案：记忆化回溯 #

核心优化点是增加记忆数组，记录每个索引位置的可达状态，避免重复计算，同时搭配词典哈希化、最长单词长度剪枝两个小优化，最终时间复杂度可降至O(n²)，可通过全部测试用例。

优化后可AC代码 #

class Solution {
    // 记忆数组状态定义：0=未访问，1=从该位置出发可拆分到末尾，-1=从该位置出发无法拆分到末尾
    int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        // 词典转HashSet实现O(1)查询，同时统计词典最长单词长度用于剪枝
        Set<String> dictSet = new HashSet<>();
        int maxWordLen = 0;
        for (String word : wordDict) {
            dictSet.add(word);
            maxWordLen = Math.max(maxWordLen, word.length());
        }
        return backtrack(s, dictSet, 0, maxWordLen);
    }

    private boolean backtrack(String s, Set<String> dictSet, int index, int maxWordLen) {
        // 到达字符串末尾，拆分成功
        if (index == s.length()) {
            return true;
        }
        // 该位置已计算过，直接返回缓存结果
        if (memo[index] != 0) {
            return memo[index] == 1;
        }
        // 前缀长度不超过词典最长单词长度，剪枝无效遍历
        int maxEnd = Math.min(index + maxWordLen, s.length());
        for (int len = 1; index + len <= maxEnd; len++) {
            String prefix = s.substring(index, index + len);
            if (dictSet.contains(prefix)) {
                if (backtrack(s, dictSet, index + len, maxWordLen)) {
                    memo[index] = 1;
                    return true;
                }
            }
        }
        // 所有前缀路径都走不通，缓存结果后返回
        memo[index] = -1;
        return false;
    }
}

内容的提问来源于stack exchange，提问作者Jessie