题解 | #单词拆分(一)#

简单思路：采用递归，每次把匹配到的前缀给去掉，然后进入下一层次的递归。直到把s变成空串，说明能够组成该单词。否则不能组成该单词。

//该版本仅能通过牛客的测试案例，但仍需完善，比如当测试用例是
//"nowcoder",["no","now","coder"]时，则会返回错误的结果，原因是没有回溯。
import java.util.*;
public class Solution {
    public boolean wordDiv (String s, String[] dic) {
        if(s.equals(""))return true;
        for(int i=0;i<=s.length();++i){
            for(int j=0;j<dic.length;++j){
                if(dic[j].equals(s.substring(0,i))){
                    return wordDiv(s.substring(i),dic);
                }
            }
        }
        return false;
    }
}
//这个版本增加了回溯功能，可以正确通过所有用例，但是仍有优化空间，至于具体如何优化，
//请读者自行思考(如何解决测试用例"11111111111...",["1","11"...]这个超时的问题？（考虑哈希表））。
import java.util.*;
public class Solution {
    boolean isExist;
    public boolean wordDiv (String s, String[] dic) {
        if(s.equals("")){
            isExist = true;
            return true;
        }
        boolean res = false;
        for(int i=0;i<=s.length();++i){
            for(int j=0;j<dic.length;++j){
                if(dic[j].equals(s.substring(0,i))){
                    res =  isExist||wordDiv(s.substring(i),dic);
                }
            }
        }
        return res;
    }
}