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;
}
}``````

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);
int[] visited = new int[s.length()];

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))) {
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()];
}
}``````

Last updated