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

import java.util.*;

/**
 * NC182 单词拆分(二)
 * @author d3y1
 */
public class Solution {
    private int len;
    private ArrayList<String> list = new ArrayList<>();

    private HashSet<String> set = new HashSet<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param dic string字符串一维数组
     * @return string字符串一维数组
     */
    public String[] wordDiv (String s, String[] dic) {
        return solution1(s, dic);
        // return solution2(s, dic);
    }

    /**
     * dfs: 字典树Trie
     * @param s
     * @param dic
     * @return
     */
    private String[] solution1(String s, String[] dic){
        Trie root = new Trie();
        for(String word: dic){
            root.insert(word);
        }

        len = s.length();
        for(int i=1; i<=len; i++){
            dfs(s, root, 0, i, "");
        }

        String[] result = new String[list.size()];
        for(int i=0; i<list.size(); i++){
            result[i] = list.get(i);
        }

        return result;
    }

    /**
     * 递归
     * @param s
     * @param root
     * @param i
     * @param j
     * @param result
     */
    private void dfs(String s, Trie root, int i, int j, String result){
        String sub = s.substring(i, j);
        if(root.search(sub)){
            if(j == len){
                list.add(result+sub);
            }else{
                String pre = s.substring(j, j+1);
                if(root.prefixNumber(pre) > 0){
                    for(int k=j+1; k<=len; k++){
                        dfs(s, root, j, k, result+sub+" ");
                    }
                }
            }
        }
    }

    /**
     * 字典树Trie
     */
    private class Trie {
        private Trie[] children;
        boolean isEnd;
        private int count;

        public Trie(){
            children = new Trie[75];
            isEnd = false;
            count = 0;
        }

        public void insert(String word){
            Trie curr = this;
            int index;
            for(char ch: word.toCharArray()){
                index = ch - '0';
                if(curr.children[index] == null){
                    curr.children[index] = new Trie();
                }
                curr = curr.children[index];
                curr.count++;
            }
            curr.isEnd = true;
        }

        public void delete(String word){
            Trie curr = this;
            int index;
            for(char ch: word.toCharArray()){
                index = ch - '0';
                if(curr.children[index] != null){
                    curr = curr.children[index];
                    curr.count--;
                }
            }
            if(curr.count == 0){
                curr.isEnd = false;
            }
        }

        public boolean search(String word){
            Trie curr = this;
            int index;
            for(char ch: word.toCharArray()){
                index = ch - '0';
                if(curr.children[index] == null){
                    return false;
                }
                curr = curr.children[index];
            }
            if(!curr.isEnd){
                return false;
            }

            return true;
        }

        public int prefixNumber(String pre){
            Trie curr = this;
            int index;
            for(char ch: pre.toCharArray()){
                index = ch - '0';
                if(curr.children[index] == null){
                    return 0;
                }
                curr = curr.children[index];
            }

            return curr.count;
        }
    }



    /**
     * dfs: HashSet
     * @param s
     * @param dic
     * @return
     */
    private String[] solution2(String s, String[] dic){
        len = s.length();
        for(String word: dic){
            set.add(word);
        }

        dfs(s, 0, "");

        String[] result = new String[list.size()];
        for(int i=0; i<list.size(); i++){
            result[i] = list.get(i).trim();
        }

        return result;
    }

    /**
     * 递归
     * @param s
     * @param i
     * @param result
     */
    private void dfs(String s, int i, String result){
        if(i == len){
            list.add(result);
        }

        String sub = "";
        // for(int j=i; j<len; j++){
        //     sub += s.charAt(j);
        //     if(set.contains(sub)){
        //         dfs(s, j+1, result+sub+" ");
        //     }
        // }
        for(int j=i+1; j<=len; j++){
            sub = s.substring(i, j);
            if(set.contains(sub)){
                dfs(s, j, result+sub+" ");
            }
        }
    }
}