【leetcode】No.140：word-break-Ⅱ

题目描述

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.

input:

s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"]

output:

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

思路：

从后往前递归地把字符串切分为两部分，后面部分如果在字典里，就放入一个list中，继续往前切分，当字符串能被分完，就从list中拿出所有切好的字符串作为一组解存入result列表中，然后后退回去，直到所有解都被找出，返回result列表。

代码：

import java.util.ArrayList;
import java.util.Set;

public class Solution {

    private ArrayList<String> resultList;
    private ArrayList<String> tmpList;

    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        resultList = new ArrayList();
        tmpList = new ArrayList();

        divide(s, dict);
        return resultList;
    }

    private void divide(String s, Set<String> dict){
        int len = s.length();
        if (len < 1){
            StringBuilder sb = new StringBuilder();
            for (int i = tmpList.size() - 1; i >= 0; i--){
                sb.append(tmpList.get(i) + " ");
            }
            sb.deleteCharAt(sb.length() - 1);
            resultList.add(sb.toString());
        }
        for (int i = len - 1; i >= 0; i--){
            String sub = s.substring(i);
            if (dict.contains(sub)){
                tmpList.add(sub);
                divide(s.substring(0, i), dict);
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }
}