Java Common template - Word Break I, Word Break II, Concatenated Words
Word Break I - Link\n Word Break II - Link \n Concatenated Words - Link\n\nCommon approach for Word Break I, Word Break II, and Concatenated Words problems. \nC
* Word Break I - [Link](https://leetcode.com/problems/word-break/)\n* Word Break II - [Link](https://leetcode.com/problems/word-break-ii/) \n* Concatenated Words - [Link](https://leetcode.com/problems/concatenated-words/)\n\nCommon approach for Word Break I, Word Break II, and Concatenated Words problems. \nConcatenated Words is the reverse process of Word Break I, hence can be broken down to Word Break I.\n\n1. Word Break I  \n      This is the top-Down approach\n\t   \n\t   class Solution { \n\t   \n\t   public boolean wordBreak(String s, List<String> wordDict) {\n        \n        // Need to use Boolean[] memo instead of boolean[], because we store both "true" and "false" in this array\n        // and need to return our pre-calculated result of "true/"false" when we hit the scenario,\n        // if it is not yet precomputed, the value will be "null"\n        \n        // If boolean[] is used, then the array will be initialized with "false", \n        // this might not be the pre-computed "false"\n        return topDown(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);\n       }\n    \n      \n\t    private boolean topDown(String s, Set<String> wordDict, int startIndex, Boolean[] memo) {\n        \n\t\t// if we reach the beyond the string, then return true\n        // s = "leetcode" when "code" is being checked in the IF() of the loop, we reach endIndex == s.length(), \n        // and wordDict.contains("code") => true and topDown(s, wordDict, endIndex, memo) needs to return true. \n        if(startIndex == s.length()) {\n            return true;\n        }\n        \n        // memo[i] = true means => that the substring from index i can be segmented. \n        // memo[startIndex] means => wordDict contains substring from startIndex and it can be segemented.\n        if(memo[startIndex] != null) { //Boolean[] array\'s default value is "null"\n            return memo[startIndex];\n        }\n        \n        for(int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {\n            if(wordDict.contains(s.substring(startIndex, endIndex)) && topDown(s, wordDict, endIndex, memo)) {\n                memo[startIndex] = true;\n                return true;\n            }\n        }\n        memo[startIndex] = false;\n        return false;\n         }\n       }\n\t  Time Complexity : O(n^3)\n\t  \n\t  \n\t  This is the bottom-up approach, where base case is dp[0] = true, because string of length 0 (empty string) is present in wordDict.\n\t   dp[i] = true => means a valid word (word that exists in wordDict) ends at index i.\n\n       class Solution {\n\t\n       public boolean wordBreak(String s, List<String> wordDict) {\n        boolean[] dp = new boolean[s.length() + 1]; //DP array to store previous results.\n        dp[0] = true; //default value.\n        \n        for(int i=1; i <= s.length(); i++){\n            for(int j=0; j < i; j++){\n                if(dp[j] && wordDict.contains(s.substring(j, i))){\n                    dp[i] = true;\n                    break;\n                }\n            }\n        }\n        return dp[s.length()];\n        }\n       }\n\nTime Complexity : O(n^3) since substring() in Java version > 7 takes O(n) time.\n\n\n\n\n2. Word Break II - use a HashMap to store previously computed results. You check given string starts with any of the words from wordDict, instead of checking every prefix of \'s\' in wordDict.\n\n       \n\t   class Solution {\t\n       public List<String> wordBreak(String s, List<String> wordDict) {\t\n        return DFS(s, wordDict, new HashMap<String, List<String>>());\n       }\n       \n\t   public List<String> DFS(String s, List<String> wordDict, Map<String, List<String>> map){\n        \n        if(map.containsKey(s)) return map.get(s);\n        \n        List<String> result = new ArrayList<>();\n        for(String word : wordDict){\n            if(s.startsWith(word)){\n               String nextWord = s.substring(word.length());\n               if(nextWord.length() == 0) \n                   result.add(word);\n               else{\n                   for(String w : DFS(nextWord, wordDict, map)) \n                       result.add(word + " " + w);\n                   } \n            }            \n        }\n        map.put(s, result);\n        return result;\n        }\n       }\n\t   \nTime Complexity: O(n^3).\nThis approach is too time consuming if the wordDict has millions of words.\n\nAnother approach based on Word Break I, where we check if every prefix of given string exists in wordDict -\n\n    class Solution {\n    \n    public Map<String, List<String>> memo = new HashMap<String, List<String>>(); \n    \n    public List<String> wordBreak(String s, List<String> wordDict) {\n        return topDown(s, new HashSet<>(wordDict), memo);\n    }\n    \n    private List<String> topDown(String s, Set<String> wordDict, Map<String, List<String>> memo) {\n        \n        if(memo.containsKey(s)) {\n            return memo.get(s);\n        }\n        \n        List<String> result = new ArrayList<String>();\n        if(wordDict.contains(s)) {\n            result.add(s);\n        }\n        \n        for(int endIndex = 1; endIndex <= s.length(); endIndex++) {\n            if(wordDict.contains(s.substring(0, endIndex))) {\n                for (String ss : topDown(s.substring(endIndex), wordDict, memo)) {\n                    result.add(s.substring(0, endIndex) + " " + ss);\n                }\n            }\n        }\n        memo.put(s, result);\n        return result;\n    }\n    }\n\n\n3. Concatenated Words - Call Word Break I function to check if a word can be concatenated by the list of words in preWords set.\n      \n\t  This is the top-down approach - \n\n       class Solution {\n       public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        //sort the array in asc order of word length, since longer words are formed by shorter words.\n        Arrays.sort(words, (a,b) -> a.length() - b.length());\n\n         List<String> result = new ArrayList<>();\n\n         //list of shorter words \n         HashSet<String> preWords = new HashSet<>();\n\n         for(int i=0; i< words.length; i++){\n             //Word Break-I problem.\n             if(topDown(words[i], preWords, 0, new Boolean[words[i].length()])) {\n                 result.add(words[i]);\n             }\n             preWords.add(words[i]);\n         }\n         return result;\n        }\n    \n       private boolean topDown(String s, HashSet<String> wordDict, int startIndex, Boolean[] memo) {\n        if(wordDict.isEmpty()) {\n            return false;\n        }\n        // if we reach the beyond the string, then return true\n        // s = "leetcode" when "code" is being checked in the IF() of the loop, we reach endIndex == s.length(), \n        // and wordDict.contains("code") => true and topDown(s, wordDict, endIndex, memo) needs to return true. \n        if(startIndex == s.length()) {\n            return true;\n        }\n        \n        // memo[i] = true means => that the substring from index i can be segmented. \n        // memo[startIndex] means => wordDict contains substring from startIndex and it can be segemented.\n        if(memo[startIndex] != null) { //Boolean[] array\'s default value is "null"\n            return memo[startIndex];\n        }\n        \n        for(int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {\n            if(wordDict.contains(s.substring(startIndex, endIndex)) && topDown(s, wordDict, endIndex, memo)) {\n                memo[startIndex] = true;\n                return true;\n            }\n        }\n        memo[startIndex] = false;\n        return false;\n       }\n       } \n\n\t  \nThis is the bottom-up approach - \n\n       class Solution {\t \n       public List<String> findAllConcatenatedWordsInADict(String[] words) {\n\t   \n        //sort the array in asc order of word length, since longer words are formed by shorter words.\n        Arrays.sort(words, (a,b) -> a.length() - b.length());\n        \n\t\tList<String> result = new ArrayList<>();\n        \n        //list of shorter words \n        HashSet<String> preWords = new HashSet<>();\n        \n        for(int i=0; i< words.length; i++){\n            //Word Break-I problem.\n            if(wordBreak(words[i], preWords)) result.add(words[i]);\n            preWords.add(words[i]);\n        }\n        return result;\n       }\n       \n\t   private boolean wordBreak(String s, HashSet<String> preWords){\n        if(preWords.isEmpty()) return false;\n        \n        boolean[] dp = new boolean[s.length() + 1];\n        dp[0] = true;\n        \n        for(int i = 1; i <= s.length(); i++){\n            for(int j = 0; j < i; j++){\n                if(dp[j] && preWords.contains(s.substring(j, i))){\n                    dp[i] = true;\n                    break;\n                }\n            }\n        }\n        return dp[s.length()];\n       }\n       }\n\t   \n\t   \nTime Complexity: O(total no.of words * (n^3)) where n = avg length of each word.\n\n
['Dynamic Programming', 'Depth-First Search', 'Java']