Sequence DP - 139. Word Break && 140. Word Break ii

139: https://leetcode.com/problems/word-break/description/140: https://leetcode.com/problems/word-break-ii/description/

139. Word Break

//     ：boolean dp[i]   s.substring(0, i)    breakable

//       :
// dp[i] = true if any index j < i, dp[j] is true && s.substring(j, i) in dictionary

//    ：boolean[] dp = new boolean[len + 1]; dp[0] = true
//    
//    target dp[len]

public boolean wordBreak(String s, List wordDict) {
    if (s == null || s.length() == 0) {
        return false;
    }
    
    int len = s.length();
    boolean[] breakable = new boolean[len + 1];
    breakable[0] = true;
    
    for (int i = 1; i <= len; i++) {
        for (int j = 0; j < i; j++) {
            if (breakable[j] && wordDict.contains(s.substring(j, i))) {
                breakable[i] = true;
                break;
            }
        }
    }
    
    return breakable[len];
}

이 제목 중 Dictionary는list이며List를 직접 사용했습니다.contains는substring이Dictionary의 워드인지 아닌지를 판단합니다. 시간 복잡도는 O (dictionary.size () 입니다.이것은 약간 유사한list가 있다.get (index) 의 시간 복잡도.LinkedList vs ArrayList. 이런 문제는 너무 진지하게 따질 필요가 없다. 직접 사용하고 복잡도 계산을 할 때 제기하면 된다. 왜냐하면 이것은 면접의 중점이 아니기 때문이다.
실제 작업에서 이러한 문제는 내부에서 사용할 때 ArrayList 또는 HashSet을 직접 성명해야 한다.불필요한 지출을 피하다.api라면 데이터의 사전 처리가 필요합니다.
이 문제는 Trie를 사용하여 구축dictionary를 미리 처리할 수 있는데 이 방법은 두 가지 상황에 특히 적합하다.dictionary가 매우 크다.2. 이 function은 호출 횟수가 매우 많다.
여기에는 string split와 dp string 에서 index의 사용 방식도 관련된다.이것은string에서 자주 발생하고 통용되는 문제입니다.여기에서 사용하는 dp는 다음과 같이 string에 대응합니다.
String value
a
b
c
d
e
string index
0
1
2
3
4
dp index
0
1
2
3
4
5
string split
0
1
2
3
4
5
dp가string에 대응하는 방식은stringsplit가string에 대응하는 방식과 일치하며,characters의 간격이 아니라characters에 대응합니다.

dp[m]는s.substring(0, m)breakable 여부;s.substring(0, m)값은characters.charAt(m)를 포함하지 않습니다.

계산dp[n] (n > m)시 대응s.substring(m, n)startingfromindexm

이런 대응 방식은 논리적으로 간단명료하고 오류가 발생하기 쉽지 않다는 것을 이해한다.

140. Word Break ii

이 제목은 모든breakable의 조합을 열거할 것을 요구합니다.DP는 139에서 최적화를 가져올 수 없다. 139에서 DP는 index에서breakable가 있는지 판단하는 것일 뿐이고 140은 index에서breakable의 모든 조합을 열거해야 하기 때문이다.직접 BackTracking:

public List wordBreakII(String s, List wordDict) {
    List res = new LinkedList<>();
    
    // to pass timeout repeated test cases.139 word break.
    if (!isBreakable(s, wordDict)) {
        return res;
    }
    
    List path = new LinkedList<>();
    helper(s, wordDict, path, res);
    return res;
}

private void helper(String str, List dictionary, List path, List res) {
    if (str.equals("")) {
        res.add(String.join(" ", path));    // Java 8
        return;
    }
    
    for (int i = 0; i < str.length(); i++) {
        String sub = str.substring(0, i + 1);
        if (dictionary.contains(sub)) {
            path.add(sub);
            helper(str.substring(i + 1), dictionary, path, res);
            path.remove(path.size() - 1);
        }
    }
}

과정 중에 모든 합법적인 결과를 기록해야 한다. 중간의 조작으로 인해 알고리즘의 복잡도는 더 이상 동적 기획의 이중 순환이 아니다. 매번 교체할 때마다 constant의 조작이 필요하기 때문에 최종 복잡도는 주로 결과의 수량에 달려 있고 대량의 공간을 차지한다. 왜냐하면 최종 결과를 보존해야 할 뿐만 아니라 중간의 합법적인 결과도 일일이 보존해야 하기 때문이다.그렇지 않으면 뒤에 역사 정보가 필요하면 찾을 수 없습니다.
9장의 Solution은 다음과 같이 직관적이다.

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        Map> memo = new HashMap>();
        return wordBreakHelper(s, dict, memo);
    }

    public ArrayList wordBreakHelper(String s,
                                             Set dict,
                                             Map> memo){
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        
        ArrayList results = new ArrayList();
        
        if (s.length() == 0) {
            return results;
        }
        
        if (dict.contains(s)) {
            results.add(s);
        }
        
        for (int len = 1; len < s.length(); ++len){
            String word = s.substring(0, len);
            if (!dict.contains(word)) {
                continue;
            }
            
            String suffix = s.substring(len);
            ArrayList segmentations = wordBreakHelper(suffix, dict, memo);
            
            for (String segmentation: segmentations){
                results.add(word + " " + segmentation);
            }
        }
        
        memo.put(s, results);
        return results;
    }
}

Trie implementation from programcreek(will implement my own version later on in Data Structures):

class TrieNode {
    TrieNode[] arr;
    boolean isEnd;

    public TrieNode() {
        this.arr = new TrieNode[26];
        this.isEnd = false;
    }
 
}
 
public class Trie {
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
 
    public void insert(String word) {
        TrieNode p = root;
        for(int i=0; i