Word Break

 

https://leetcode.com/problems/word-break

class Solution {
    boolean[] isChecked; 
    Map<String, String> hash;
    String str;
    boolean isComplete = false;
    
    public boolean wordBreak(String s, List<String> wordDict) {
        isChecked = new boolean[s.length()];
        hash = new HashMap<>();
        str = s;
        
        for(String word: wordDict) {
            hash.put(word, word);
        }
        
        rec(0);
        return isComplete;
    }
    
    void rec(int start) {
        if(isChecked[start]) return;
        
        StringBuffer sb = new StringBuffer();
        
        for(int i=start; i<str.length(); i++) {
            sb.append(str.charAt(i));
            
            if(hash.containsKey(sb.toString())) {
                if(i+1 == str.length()){
                    isComplete = true;
                    return;    
                }
                rec(i+1);
            }
        }
        isChecked[start] = true;
    }
}

 

 

 

재귀 + 메모제이션 (DP)