LeetCode | Word Break II

题目

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

直接的思路就是用动态规划，实现中要注意：

1. 需要加上备忘录，避免超时；

2. 需要判断句子是否能正确分割，下述代码中，利用null来标识不能分割的子句；

3. 下述代码中，没有在意空间，备忘录中直接纪录了各个子句的字符串分割结果；如果空间上有所限制的话，可以在备忘录中纪录分割点的索引，最后再生成结果；

4. 进一步提升性能的话，可以左右同时开工，建立二维的备忘录。

代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class WordBreakII {
	private Map
  
   > records = new HashMap
   
    >(); private Set
    
      dict = null; private String s = null; private int N = 0; public ArrayList
     
       wordBreak(String s, Set
      
        dict) { // Note: The Solution object is instantiated only once and is reused by // each test case. if (s == null || s.length() <= 0 || dict == null || dict.size() <= 0) { return new ArrayList
       
        (); } records.clear(); this.dict = dict; this.s = s; N = s.length(); ArrayList
        
          list = solve(0); if (list == null) { list = new ArrayList
         
          (); } return list; } private ArrayList
          
            solve(int i) { if (records.containsKey(i)) { return records.get(i); } ArrayList
           
             list = new ArrayList
            
             (); if (i >= N) { records.put(i, list); return list; } for (int j = i + 1; j <= N; ++j) { String word = s.substring(i, j); if (dict.contains(word)) { ArrayList
             
               subList = solve(j); ArrayList
              
                newList = new ArrayList
               
                (); if (subList == null) { continue; } else if (subList.size() == 0) { newList.add(word); } else { for (String result : subList) { newList.add(word + " " + result); } } list.addAll(newList); } } if (list.size() == 0) { list = null; } records.put(i, list); return list; } }