139. Word Break (Medium)

https://leetcode.com/problems/word-break/

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Solutions

class Solution {

    // keep track of the substrings that are able to partition
    Set<String> partitionable = new HashSet<>();

    // keep track of the substrings that are unable to partition
    Set<String> unpartitionable = new HashSet<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        // See if s or wordDict is null
        if (s == null || s.length() == 0 || wordDict == null || wordDict.isEmpty()) {
            return false;
        }

        // transfer words from List to Set
        Set<String> dict = new HashSet<>(wordDict);

        // recursively break up the strings, return the possible combinations
        return recurse(s, dict);
    }

    private boolean recurse(String str, Set<String> dict) {
        // return tree if reach the end
        if (str == null || str.isEmpty()) {
            return true;
        }

        // return null if str is unpartitionable.
        if (unpartitionable.contains(str)) {
            return false;
        }

        // return true if str is previously partitioned.
        if (partitionable.contains(str)) {
            return true;
        }

        // keep the count of the possible partition schemes
        int count = 0;

        // try all the possible splitting schemes, i is the length of current substring.
        for (int i = 1; i <= str.length(); i++) {
            String sub = str.substring(0, i);
            if (!dict.contains(sub)) {
                continue;
            }

            boolean result = recurse(str.substring(i), dict);

            // str.substring(i) can not be partitioned.
            if (!result) {
                continue;
            }

            count++;
        }

        // if no partition scheme available, keep this substring to black list
        if (count == 0) {
            unpartitionable.add(str);

            // must return null, otherwise previous level will take it partitionable.
            return false;
        }

        // At least 1 partition scheme

        partitionable.add(str);

        return true;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-04 01:54:30

results matching ""

    No results matching ""