import type { Trie } from '../src' ; import { createTrie , lowercaseIdx } from '../src' ; test ( 'word-search-ii' , function ( ) { const data = [ { input : [ [ [ 'o' , 'a' , 'a' , 'n' ] , [ 'e' , 't' , 'a' , 'e' ] , [ 'i' , 'h' , 'k' , 'r' ] , [ 'i' , 'f' , 'l' , 'v' ] , ] , [ 'oath' , 'pea' , 'eat' , 'rain' ] , ] , answer : [ 'oath' , 'eat' ] , } , { input : [ [ [ 'a' , 'b' ] , [ 'c' , 'd' ] , ] , [ 'abcb' ] , ] , answer : [ ] , } , ] ; for ( const { input , answer } of data ) { expect ( findWords ( input [ 0 ] , input [ 1 ] ) ) . toEqual ( answer ) ; } } ) ; author guanghechen
  function findWords ( board , words ) { if ( words . length === 0 ) return [ ] ; const R = board . length ; if ( R <= 0 ) return [ ] ; const C = board [ 0 ] . length ; if ( C <= 0 ) return [ ] ; const trie = createTrie ( { SIGMA_SIZE : 26 , ZERO : 0 , idx : lowercaseIdx , mergeAdditionalValues : x => x , } ) ; trie . init ( ) ; const visited = new Array ( R ) ; for ( let r = 0 ; r < R ; ++ r ) visited [ r ] = new Array ( C ) . fill ( false ) ; const boardWord = [ ] ; for ( let r = 0 ; r < R ; ++ r ) { for ( let c = 0 ; c < C ; ++ c ) { dfs ( 0 , r , c ) ; } } const results = [ ] ; for ( const word of words ) { if ( trie . hasPrefixMatched ( word ) ) results . push ( word ) ; } return results ; function dfs ( cur , r , c ) { if ( cur === 10 || r < 0 || r >= R || c < 0 || c >= C ) { trie . insert ( boardWord . join ( '' ) , 1 , 0 , cur ) ; return ; } if ( visited [ r ] [ c ] ) return ; visited [ r ] [ c ] = true ; boardWord [ cur ] = board [ r ] [ c ] ; const nextCur = cur + 1 ; dfs ( nextCur , r - 1 , c ) ; dfs ( nextCur , r , c + 1 ) ; dfs ( nextCur , r + 1 , c ) ; dfs ( nextCur , r , c - 1 ) ; visited [ r ] [ c ] = false ; } }