| 162 | }; |
| 163 | |
| 164 | var initTabu = (word1, word2) => { |
| 165 | const tabu = new Array(word1.length + 1) |
| 166 | .fill() /* Time O(N) | Space O(N) */ |
| 167 | .map(() => |
| 168 | new Array(word2.length + 1).fill(0), |
| 169 | ); /* Time O(M) | Space O(M) */ |
| 170 | |
| 171 | for (let i = 0; i < word1.length + 1; i++) { |
| 172 | /* Time O(N) */ |
| 173 | tabu[i][0] = i; /* | Space O(N * M) */ |
| 174 | } |
| 175 | |
| 176 | for (let j = 0; j < word2.length + 1; j++) { |
| 177 | /* Time O(M) */ |
| 178 | tabu[0][j] = j; /* | Space O(N * M) */ |
| 179 | } |
| 180 | |
| 181 | return tabu; |
| 182 | }; |
| 183 | |
| 184 | var search = (word1, word2, tabu) => { |
| 185 | for (let i = 1; i < word1.length + 1; i++) { |