Word Break 2

Word Break II

문제 내용 및 풀이 방법은

2020.09.29 - [Problem Solving] - 139. Word Break

와 동일하다.

다른 점이 있다면 word break 1번 문제는 Dictionary로 해당 문자를 만들 수 있는가?

이고 word break 2번 문제는 모든 경우의 수를 return 하는 것이 다르다.

    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, new HashMap<>());
    }


    public ArrayList<String> dfs(String s, List<String> wordDict, HashMap<String, ArrayList> dp) {
        ArrayList<String> result = new ArrayList<>();

        if (dp.containsKey(s)) {
            return dp.get(s);
        }

        for (String word : wordDict) {
            if (s.startsWith(word)) {
                if (word.length() == s.length()) {
                    result.add(word);
                } else {
                    ArrayList<String> tmpArr = dfs(s.substring(word.length()), wordDict, dp);

                    if(0 < tmpArr.size()){
                        for(String tmpWord : tmpArr){
                            result.add(word + " " + tmpWord);
                        }
                    }
                }
            }
        }

        dp.put(s, result);

        return result;
    }

Word break에서도 그랬지만 Trie는 불필요 하다.

Time Complexity는 최악의 경우

s가 1 character size로 잘리고 Word dictionary를 모두 Search해야 하는 경우로 계산 해야한다.

["aaa"] ["a","b",,,,"z","aa","ab"....."zzzzz..."]

그래서

$$ O( S Length * dictionary size) $$

이다