139.Word-Break

139. Word Break

题目地址

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

代码

Approach 1: Brute Force

Complexity Analysis

• Time complexity : O(n^n). Consider the worst case where s = "aaaaaaa" and every prefix of s is present in the dictionary of words, then the recursion tree can grow upto n^n.

• Space complexity : O_(_n). The depth of the recursion tree can go upto n_n*.

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, new HashSet(wordDict), 0);
  }

  public boolean dfs(String s, Set<String> wordDict, int start) {
    if (start == s.length()) {
      return true;
    }
    for (int end = start + 1; end <= s.length(); end++) {
      if (wordDict.contains(s.substring(start, end)) && 
          dfs(s, wordDict, end)) {
        return true;
      }
    }

    return false;
  }
}

Approach #2 Recursion with memoization

Complexity Analysis

• Time complexity : O(n^2). Size of recursion tree can go up to n^2.

• Space complexity : O(n). The depth of recursion tree can go up to n.

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
  }

  public boolean dfs(String s, Set<String> wordDict, int start, Boolean[] memo) {
    if (start == s.length()) {
      return true;
    }

    if (memo[start] != null) {
      return memo[start];
    }

    for (int end = start + 1; end <= s.length(); end++) {
      if (wordDict.contains(s.substring(start, end)) 
          && dfs(s, wordDict, end, memo)) {
        return memo[start] = true;
      }
    }

    return memo[start] = false;
  }
}

Approach #3 Using Breadth-First Search

Complexity Analysis

• Time complexity : O(n^2). For every starting index, the search can continue till the end of the given string.

• Space complexity : O_(_n). Queue of atmost n size is needed.

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    Queue<Integer> queue = new LinkedList<>();
    int[] visited = new int[s.length()];

    queue.add(0);
    while (!queue.isEmpty()) {
      int start = queue.remove();
      if (visited[start] == 0) { // 这一步判断很关键，不然会超时
        for (int end = start + 1; end <= s.length(); end++) {
          if (wordDictSet.contains(s.substring(start, end))) {
            queue.add(end);
            if (end == s.length()) {
              return true;
            }
          }
        }

        visited[start] = 1;
      }
    }

    return false;
  }
}

Approach #4 Using Dynamic Programming

Complexity Analysis

• Time complexity : O(n^2). Two loops are their to fill dp array.

• Space complexity : O_(_n). Length of p array is n + 1.

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    boolean[] dp = new boolean[s.length() + 1];

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

    return dp[s.length()];
  }
}