## Saturday, 5 June 2021

### Java Program To Solve Word Break Problem

Given a string A and a dictionary of words B, find out if A can be segmented into a space-separated sequence of dictionary words.

``````Input:
A = "myinterviewtrainer",
B = ["trainer", "my", "interview"]

Output:
1 ("myinterviewtrainer" can be segmented as "my interview trainer")

Input:
A = "cc"
B = ["ccc"]

Output:
0 ("cc" can't be segmented as "ccc")``````
Word break problem can be solved using dynamic programming. We solved the problem in bottom up manner. The result array contains n+1 elements where n is length of A. The base case of empty string ("") is true. Then we begin with the first letter of A & loop till end. There is one inner loop, so time complexity is O(n^2). I am not considering time complexity of finding the substring in List B. It can be converted to Map & find Operation can be done in O(1).

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22``` ```import java.util.*; import java.lang.*; import java.io.*; class Solution { public int wordBreak(String A, ArrayList B) { int[] result = new int[A.length() + 1]; //for empty string wordbreak is true result = 1; for(int i=0; i

### Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...