Find largest word in dictionary by deleting some characters of given string | Returns true if str1 [ ] is a subsequence of str2 [ ] . m is length of str1 and n is length of str2 ; Traverse str2 and str1 , and compare current character of str2 with first unmatched char of str1 , if matched then move ahead in str1 ; If all characters of str1 were found in str2 ; Returns the longest string in dictionary which is a subsequence of str . ; Traverse through all words of dictionary ; If current word is subsequence of str and is largest such word so far . ; Return longest string ; Driver code
< ? php function isSubSequence ( $ str1 , $ str2 ) { $ m = strlen ( $ str1 ) ; $ n = strlen ( $ str2 ) ; for ( $ i = 0 ; $ i < $ n && $ j < $ m ; $ i ++ ) if ( $ str1 [ $ j ] == $ str2 [ $ i ] ) $ j ++ ; return ( $ j == $ m ) ; } function findLongestString ( $ dict , $ str ) { $ result = " " ; $ length = 0 ; foreach ( $ dict as $ word ) { if ( $ length < strlen ( $ word ) && isSubSequence ( $ word , $ str ) ) { $ result = $ word ; $ length = strlen ( $ word ) ; } } return $ result ; } $ dict = array ( " ale " , " apple " , " monkey " , " plea " ) ; $ str = " abpcplea " ; echo findLongestString ( $ dict , $ str ) ; ? >