Word splitting

Title Description: given a non empty string s and a list wordDict containing non empty words, determine whether s can be divided into one or more words in the dictionary by spaces.

explain:

• Words in the dictionary can be reused when splitting.
• You can assume that there are no duplicate words in the dictionary.

See LeetCode's official website for an example.

Source: LeetCode
Link: https://leetcode-cn.com/problems/word-break/
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

Solution 1: exhaustive method

The method of exhaustion + recursion is used to solve, which is inefficient. The specific processing process is as follows:

• If the current string is null or empty, it can be segmented by the string dictionary by default and return true directly;
• Otherwise, traverse the string in the string dictionary:
  • If a string is exactly equal to the current string and has the same length, it will directly return true;
  • If a string is equal to the current string but the length is inconsistent, recursively judge the subsequent string and return the judgment result.
• Finally, the final judgment result is returned.

Solution 2: dynamic programming

• Firstly, initialize the string dictionary into the hash table wordDictSet to facilitate fast search;
• Then initialize a dp array whose length is the length of the original string plus 1, and initialize the first element of the array to true;
• Then traverse the string to determine whether the string from 0 to i can be segmented by the string dictionary:
  • The judgment logic is that the string from 0 to j can be segmented by the string dictionary (this is calculated according to the previous calculation), and the string from j to i is in the string dictionary.
• Finally, the last element of the returned dp array is the final result.

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

public class LeetCode_139 {
    private static boolean flag = false;

    /**
     * Exhaustive method
     *
     * @param s
     * @param wordDict
     * @return
     */
    public static boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }

        for (String word : wordDict) {
            if (flag) {
                return flag;
            }
            if (s.startsWith(word)) {
                if (s.length() == word.length()) {
                    // If the current character matches a string in the string dictionary and the length is the same, it indicates that the current string can be cut by the string dictionary and returns true
                    return true;
                }
                // If there are still characters to be judged after the current string is segmented by a string in a string dictionary, the following string will be judged recursively
                flag = wordBreak(s.substring(word.length()), wordDict);
            }
        }
        return flag;
    }

    /**
     * dynamic programming
     *
     * @param s
     * @param wordDict
     * @return
     */
    public static boolean wordBreak2(String s, List<String> wordDict) {
        // Initialize the string dictionary into the hash table for quick lookup
        Set<String> wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        // The default empty string can be segmented from the string dictionary and initially set to true
        dp[0] = true;

        // Judge whether the string from 0 to i can be segmented by the string dictionary
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // The judgment logic is that the string from 0 to j can be segmented by the string dictionary (this is calculated according to the previous calculation), and the string from j to i is in the string dictionary
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        String s = "applepenapple";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("apple");
        wordDict.add("pen");

        System.out.println(wordBreak(s, wordDict));
        System.out.println(wordBreak2(s, wordDict));
    }
}

[daily message] believe that opportunities always exist. Don't compete with yourself. Follow the trend, just like tai chi pushing hands. Learn to make use of surrounding resources.