LeetCode刷题【140】单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

题解

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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private List<String> res = new ArrayList<>();
    private HashSet<String> hashSet;
    private String testString;

    public List<String> wordBreak(String s, List<String> wordDict) {
        char[] chars = s.toCharArray();
        hashSet = new HashSet<>(wordDict);
        testString = s;
        List<String> stringList = new ArrayList<>();
        traceback(0,stringList);
        return res;
    }


    /**
     * 回溯模板
     * 这里的边界需要仔细考虑下。不过可以套个简单的方法
     * 假如字符串长度为1，那么截取的话应该是从index=0，截取到index=1
     * 所以最终的终止位置应该是和字符串的长度一致的
     */
    private void traceback(int startPosition,List<String> stringList){
        if (startPosition == testString.length()){
            res.add(listToString(stringList));
        }
        for (int endPosition = startPosition+1;endPosition<= testString.length();endPosition++){
            String subString = testString.substring(startPosition,endPosition);
//            System.out.println(subString);
            if (!hashSet.contains(subString)){
                continue;
            }
            stringList.add(subString);
            //向下嵌套
            traceback(endPosition,stringList);
            //退一次操作
            stringList.remove(stringList.size()-1);
        }
    }


    /**
     * 数组转换字符串的方法
     * @param stringList
     * @return
     */
    private String listToString(List<String> stringList){
        StringBuilder sb = new StringBuilder();
        for (String str: stringList){
            if (sb.length()>0){
                sb.append(" ");
            }
            sb.append(str);
        }
        return sb.toString();
    }

}
//leetcode submit region end(Prohibit modification and deletion)