word-search.dart (2727B)
1 //Given a word search through the board and return true 2 //if you can make the word from the board by moving only left 3 //right up and down without reusing the same tiles. 4 //I used recursion and backtracking to check all possible routes 5 //to see if any tiles with the same starting tile as word 6 //could be used to make the word. I also implemented a check at the start 7 //to iterate through the matrix to verify that at least all of the characters being 8 //looked for exist in the matrix before starting the search. 9 //Time: 2869ms Beats: 50% 10 //Memory: 185.2MB Beats: 50% 11 class Solution { 12 bool exist(List<List<String>> board, String word) { 13 Set<String> letters = {}; 14 for(int i = 0 ; i < word.length ; ++i){ 15 letters.add(word[i]); 16 } 17 for(int i = 0 ; i < board.length ; ++i){ 18 for(int x = 0 ; x < board[i].length ; ++x){ 19 letters.remove(board[i][x]); 20 } 21 } 22 if(letters.length != 0){ 23 return false; 24 } 25 for(int i = 0 ; i < board.length ; ++i){ 26 for(int x = 0 ; x < board[i].length ; ++x){ 27 if(board[i][x] == word[0]){ 28 if(find(board,word, [i,x] , {})){ 29 return true; 30 } 31 } 32 } 33 } 34 return false; 35 } 36 37 bool find(List<List<String>> board , String word , List<int> current_position, Set<String> visited){ 38 String curr_str = current_position[0].toString() + " " + current_position[1].toString(); 39 if(visited.contains(curr_str)){ 40 return false; 41 } 42 visited.add(curr_str); 43 if(word.length == 0 || (word.length == 1 && board[current_position[0]][current_position[1]] == word)){ 44 return true; 45 } 46 if(word[0] != board[current_position[0]][current_position[1]]){ 47 return false; 48 } 49 int curry = current_position[1]; 50 int currx = current_position[0]; 51 52 bool left = false; 53 bool right = false; 54 bool down = false; 55 bool up = false; 56 57 if(curry != 0){ 58 up = find(board , word.substring(1) , [currx, curry - 1], Set.from(visited)); 59 } 60 if(up){ 61 return true; 62 } 63 if(currx != 0){ 64 left = find(board , word.substring(1) , [currx - 1, curry], Set.from(visited)); 65 } 66 if(left){ 67 return true; 68 } 69 if(currx != board.length - 1){ 70 right = find(board , word.substring(1) , [currx + 1, curry], Set.from(visited)); 71 } 72 if(right){ 73 return true; 74 } 75 if(curry != board[0].length - 1){ 76 down = find(board , word.substring(1) , [currx, curry + 1], Set.from(visited)); 77 } 78 if(down){ 79 return true; 80 } 81 82 return false; 83 } 84 }