Leetcode 139: 单词切分

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
    注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

思路

思路1：暴力遍历（时间爆表）

检查每一个前缀的子字符串回溯实现

思路2：记忆化可切分后缀

记录一个回溯记忆数组，若该后缀可切分则综合到最后可切分，这样可以大幅减少调用函数次数

思路3: BFS实现

使用广度优先遍历实现，相当于将可到达相同的前缀节点合并，不进行相同的后续操作，减少函数调用次数。

思路4: DP实现

第j个位置可根据可形成前缀的位置进行计算，若其前缀为i,则若s.sub(i, j)在字典中则第j个位置为可拼接，最后一个位置即为最后是否可切分结果。

代码

代码1

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        } else if (wordDict.size() == 0) {
            return false;
        }
        HashSet hashSet = new HashSet<>(wordDict);
        return wordBreakHelper(s, 0, hashSet);

    }

    private boolean wordBreakHelper(String s, int startIndex, HashSet hashSet) {
        if (startIndex >= s.length()) {
            return true;
        }
        boolean hasMatch = false;
        for(var neededStr: hashSet) {
//            System.out.println(s.substring(startIndex, startIndex + neededStr.length()));
            if (startIndex + neededStr.length() <= s.length() && s.substring(startIndex, startIndex + neededStr.length()).equalsIgnoreCase(neededStr)) {
                hasMatch = hasMatch || wordBreakHelper(s, startIndex + neededStr.length(), hashSet);
                if (hasMatch) {
                    break;
                }
            }
        }
        return hasMatch;
    }
}

代码2

public class Solution2 {
    public boolean wordBreak(String s, List wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        } else if (wordDict.size() == 0) {
            return false;
        }
        HashSet hashSet = new HashSet<>(wordDict);
        return wordBreakHelper(s, 0, hashSet, new Boolean[s.length()]);
    }

    private boolean wordBreakHelper(String neededStr, int startIndex, HashSet hashSet, Boolean[] hasMatch) {
        if (startIndex == neededStr.length()) {
            return true;
        }
        if (hasMatch[startIndex] != null) {
            return hasMatch[startIndex];
        }
        for(int i=startIndex + 1; i <= neededStr.length(); i++) {
            if (hashSet.contains(neededStr.substring(startIndex, i)) && wordBreakHelper(neededStr, i, hashSet, hasMatch)) {
                return hasMatch[startIndex] = true;
            }
        }
        return hasMatch[startIndex] = false;
    }
}

代码3：BFS （队列实现）

public class Solution3 {
    public boolean wordBreak(String s, List wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        } else if(wordDict.size() == 0) {
            return false;
        }
        Set hashSet = new HashSet<>(wordDict);
        Queue queue = new LinkedList<>();
        boolean[] hasSeen = new boolean[s.length()];
        queue.add(0);
        while (!queue.isEmpty()) {
            int startIndex = queue.remove();
            if (!hasSeen[startIndex]) {
                for(int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {
                    if (hashSet.contains(s.substring(startIndex, endIndex))) {
                        queue.add(endIndex);
                        if (endIndex == s.length()) {
                            return true;
                        }
                    }
                }
                hasSeen[startIndex] = true;
            }
        }
        return false;
    }
}

代码4: DP实现

public class Solution4 {
    public boolean wordBreak(String s, List wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        } else if(wordDict.size() == 0) {
            return false;
        }
        Set hashSet = new HashSet<>(wordDict);
        boolean[] dps = new boolean[s.length() + 1];
        dps[0] = true;

        for(int end = 1; end < s.length() + 1; end++) {
            for(int start=0; start < end; start++) {
                if (dps[start] && hashSet.contains(s.substring(start, end))) {
                    dps[end] = true;
                    break;
                }
            }
        }
        return dps[s.length()];
    }
}

复杂度分析

思路1：时间复杂度

$n^n$

思路1: 空间复杂度

$n$

思路2: 时间复杂度

$n^2$

思路2：空间复杂度

$n$

思路3: 时间复杂度

$n^2$

思路3：空间复杂度

$n$

思路4: 时间复杂度

$n^2$

思路4：空间复杂度

$n$

总结

重点在于如何将重复或者非必需的步骤省略