word-break.dart (1470B)
1 //Given an input lsit wordDict return true if you can create 2 //the String s using only strings from the wordDict list. 3 4 //To solve this I first created a set with the word list 5 //because constant time search is better than linear, and repeats 6 //do not matter for this. I then iterated through the string 7 //from the start to end checking to see if the current substring 8 //is contained in the set. If it is then I removed the first part of the string 9 //and recursed. From here I added the length of the new string to the memo set 10 //so that I do not check the same path twice. If the string is of length 0 11 //that means all substrings can be removed from the string and thus it can be made. 12 13 //Time: 217ms Beats: 100% 14 //Memory: 141.9MB Beats: 62.50% 15 16 class Solution { 17 Set<String> dictionary = {}; 18 Set<int> memo = {}; 19 bool wordBreak(String s, List<String> wordDict) { 20 if(memo.contains(s.length)){ 21 return false; 22 } 23 if(s.length == 0){ 24 return true; 25 } 26 if(dictionary.length == 0){ 27 for(String str in wordDict){ 28 dictionary.add(str); 29 } 30 } 31 for(int i = 1 ; i < s.length + 1 ; ++i){ 32 String sub = s.substring(0,i); 33 if(dictionary.contains(sub)){ 34 String check = s.substring(i); 35 if(wordBreak(check, wordDict)){ 36 return true; 37 } 38 memo.add(check.length); 39 } 40 } 41 return false; 42 } 43 }