import type { Trie } from '../src' ; import { createTrie , lowercaseIdx } from '../src' ; test ( 'word-break-ii' , function ( ) { const data = [ { input : [ 'catsanddog' , [ 'cat' , 'cats' , 'and' , 'sand' , 'dog' ] ] , answer : [ 'cat sand dog' , 'cats and dog' ] , } , { input : [ 'pineapplepenapple' , [ 'apple' , 'pen' , 'applepen' , 'pine' , 'pineapple' ] , ] , answer : [ 'pine apple pen apple' , 'pine applepen apple' , 'pineapple pen apple' , ] , } , { input : [ 'catsandog' , [ 'cats' , 'dog' , 'sand' , 'and' , 'cat' ] ] , answer : [ ] , } , ] ; for ( const { input , answer } of data ) { expect ( wordBreak ( input [ 0 ] , input [ 1 ] ) ) . toEqual ( answer ) ; } } ) ; author guanghechen
  function wordBreak ( s , wordDict ) { if ( s . length <= 0 ) return [ ] ; const trie = createTrie ( { SIGMA_SIZE : 26 , ZERO : 0 , idx : lowercaseIdx , mergeAdditionalValues : ( x , y ) => y , } ) ; trie . init ( ) ; for ( let i = 0 ; i < wordDict . length ; ++ i ) { const word = wordDict [ i ] ; trie . insert ( word , i + 1 ) ; } const N = s . length ; const results = [ ] ; const collect = [ ] ; dfs ( 0 , 0 ) ; return results ; function dfs ( cur , pos ) { if ( pos === N ) { results . push ( collect . slice ( 0 , cur ) . map ( x => wordDict [ x - 1 ] ) . join ( ' ' ) ) ; return ; } const pairs = trie . findAll ( s , pos ) ; for ( const { end , val } of pairs ) { collect [ cur ] = val ; dfs ( cur + 1 , end ) ; } } }