| 104 | }; |
| 105 | |
| 106 | var search = (text, pattern, tabu) => { |
| 107 | for (let row = text.length; 0 <= row; row--) { |
| 108 | /* Time O(N) */ |
| 109 | for (let col = pattern.length - 1; 0 <= col; col--) { |
| 110 | /* Time O(M) */ |
| 111 | const isTextDefined = row < text.length, |
| 112 | isTextAndPatternEqual = pattern[col] === text[row], |
| 113 | isPatternPeriod = pattern[col] === '.', |
| 114 | isFirstMatch = |
| 115 | isTextDefined && (isTextAndPatternEqual || isPatternPeriod), |
| 116 | isNextPatternWildCard = |
| 117 | col + 1 < pattern.length && pattern[col + 1] === '*'; |
| 118 | |
| 119 | tabu[row][col] = isNextPatternWildCard /* Space O(N * M) */ |
| 120 | ? tabu[row][col + 2] || (isFirstMatch && tabu[row + 1][col]) |
| 121 | : isFirstMatch && tabu[row + 1][col + 1]; |
| 122 | } |
| 123 | } |
| 124 | }; |