This article is participating in “Java Theme Month – Java Swipe Card”, see the activity link for details

A, the titleThe word split

Given a non-empty string s and a list wordDict containing non-empty words, determine whether s can be split by Spaces into one or more words that occur in the dictionary.

  • Description:
    • You can reuse words from the dictionary when you break them up.
    • You can assume that there are no duplicate words in the dictionary.
  • Example:
    • Type: s = “leetcode”, wordDict = [“leet”, “code”]
    • Output: true,
    • Explanation: Returns true because “leetcode” can be split into “leetcode”.

Second, the analysis

If the string s can be split into words, then there must be j such that both s.substring(j) and S.substring (j,slen+1) substrings can be split into words. Similarly, two substrings exist in the same property as the string s. We can then traverse s.length() from 0, recording whether the substring before each position can be split into multiple words.

Determine the meaning of dp array and subscript

Dp [I]: S.substring (I) can be split into words. Note: dp[I] should record whether the position of the string subscript i-1 can be split into multiple words.

Determine the recurrence formula

For DP [I], if s.substring(I) can be split into words, then there must be j such that s.substring(j) substring can be split into words, and s.substring(j, I) substring is one word. Dp [I] = dp[j] && worddict.contains (s.substring(j, I)).

Dp array initialization

Dp [0] represents the case of an empty substring. Given a non-empty string, the null substring should be meaningless in this case. However, dp[I] depends on dp[j]. If dp[0] is false, then whether dp[I] is true or not is irrelevant, so dp[0] must be true.

Traversal sequence

In this case, we use a two-level loop traversal. The outer loop naturally traverses from 0 to s.length(). For the inner layer, traversing from I to 1 can significantly reduce the number of loops.

Example to derive the DP array

Three, code implementation

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int sLength = s.length();
        boolean[] dp = new boolean[sLength+1];
        dp[0] = true;
        for(int i = 1; i <= sLength; i++){
            for (int j = i; j >= 0; j--){
                if(dp[j] && wordSet.contains(s.substring(j,i))){
                    dp[i] = true;
                    break; }}}returndp[sLength]; }}Copy the code

Fourth, advanced

140. What do you mean

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int len = s.length();

        // Step 1: Dynamic programming calculates whether there is a solution
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int right = 1; right <= len; right++) {
            // It is faster to iterate from back to front
            for (int left = right - 1; left >= 0; left--) {
                if (wordSet.contains(s.substring(left, right)) && dp[left]) {
                    dp[right] = true;
                    break; }}}// Step 2: The backtracking algorithm searches for all the qualified solutions
        List<String> res = new ArrayList<>();
        if (dp[len]) {
            Deque<String> path = new ArrayDeque<>();
            dfs(s, len, wordSet, dp, path, res);
            return res;
        }
        return res;
    }

    /** * s[0:len] if you can split wordSet into words, add the result of recursion to res **@param s
     * @paramLen The prefix substring * of s of length len@paramWordSet Set of words that have been added to the hash table *@paramThe dp array * obtained by dp preprocessing@paramPath Path * from the leaf to the root@paramRes holds the variable */ for all results
    private void dfs(String s, int len, Set<String> wordSet, boolean[] dp, Deque<String> path, List<String> res) {
        if (len == 0) {
            res.add(String.join("",path));
            return;
        }

        // The left margin that can be split is enumerated from Len - 1 to 0
        for (int i = len - 1; i >= 0; i--) {
            String suffix = s.substring(i, len);
            if(wordSet.contains(suffix) && dp[i]) { path.addFirst(suffix); dfs(s, i, wordSet, dp, path, res); path.removeFirst(); }}}}Copy the code