Added solution for Word breaks.

anxious-coder-lhs · anxious-coder-lhs · commit 9a42dc89fa6b · 2020-11-05T12:53:26.000+05:30
diff --git a/level_medium/WordBreak_1.ts b/level_medium/WordBreak_1.ts
@@ -0,0 +1,48 @@
+function wordBreak(s: string, wordDict: string[]): boolean {
+    const result: {[k: number]: boolean} = {}
+    wordDict.forEach(word => result[word.length] = true)
+    const dictSizes = Object.keys(result).map(l => parseInt(l));
+    const wordSet = new Set(wordDict);
+    
+    // Init the DP table for memoization and solve recursively.
+    const dp: boolean[][] = Array.from({length: s.length})
+    return wordBreakHelper(s, wordSet, dictSizes, 0, s.length, dp)
+};
+
+function wordBreakHelper(s: string, wordSet: Set<string>, dictSizes: number[], beg: number, end: number, dp: boolean[][]): boolean {
+    
+    // Base Condition, returns true.
+    if (beg >= end) {
+        return true;
+    }
+    
+    for (let idx = 0; idx < dictSizes.length; idx++) {
+        const gap = dictSizes[idx];
+        const term = beg + gap;
+        if (term <= end && contains(s, wordSet, beg, term)) {
+            
+            // Init dp.
+            dp[term] = dp[term] || [];
+            
+            if (dp[term][end] === undefined) {
+                dp[term][end] = wordBreakHelper(s, wordSet, dictSizes, term, end, dp)
+            }
+                
+            if (dp[term][end]) {
+                dp[beg] = dp[beg] || [];
+                dp[beg][end] = true;
+                return dp[beg][end];    
+            }
+        }
+    }
+    
+    dp[beg] = dp[beg] || [];
+    dp[beg][end] = false;
+    return dp[beg][end];
+}
+
+function contains(s: string, wordSet: Set<string>, beg: number, end: number) {
+    const slice = s.slice(beg, end)
+    console.log(slice)
+    return wordSet.has(slice);
+}
diff --git a/level_medium/WordBreak_2.ts b/level_medium/WordBreak_2.ts
@@ -0,0 +1,40 @@
+function wordBreak(s: string, wordDict: string[]): boolean {
+    const wordSet = new Set(wordDict);
+    const dp: boolean[][] = Array.from({length: s.length})
+    return wordBreakHelper(s, wordSet, 0, s.length, dp)
+};
+
+function wordBreakHelper(s: string, wordSet: Set<string>, beg: number, end: number, dp: boolean[][]): boolean {
+    
+    // Base Condition, returns true.
+    if (beg >= end) {
+        return true;
+    }
+    
+    for (let term = beg + 1; term <= end; term++) {
+        if (term <= end && contains(s, wordSet, beg, term)) {            
+            
+            // Init dp.
+            dp[term] = dp[term] || [];
+            
+            if (dp[term][end] === undefined) {
+                dp[term][end] = wordBreakHelper(s, wordSet, term, end, dp)
+            }
+                
+            if (dp[term][end]) {
+                dp[beg] = dp[beg] || [];
+                dp[beg][end] = true;
+                return dp[beg][end];    
+            }
+        }   
+    }
+    
+    dp[beg] = dp[beg] || [];
+    dp[beg][end] = false;
+    return dp[beg][end];
+}
+
+function contains(s: string, wordSet: Set<string>, beg: number, end: number) {
+    const slice = s.slice(beg, end)
+    return wordSet.has(slice);
+}
diff --git a/package-lock.json b/package-lock.json
