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 program to test above function
def isSubSequence ( str1 , str2 ) : NEW_LINE INDENT m = len ( str1 ) ; NEW_LINE n = len ( str2 ) ; NEW_LINE i = 0 ; NEW_LINE while ( i < n and j < m ) : NEW_LINE INDENT if ( str1 [ j ] == str2 [ i ] ) : NEW_LINE INDENT j += 1 ; NEW_LINE DEDENT i += 1 ; NEW_LINE DEDENT return ( j == m ) ; NEW_LINE DEDENT def findLongestString ( dict1 , str1 ) : NEW_LINE INDENT result = " " ; NEW_LINE length = 0 ; NEW_LINE for word in dict1 : NEW_LINE INDENT if ( length < len ( word ) and isSubSequence ( word , str1 ) ) : NEW_LINE INDENT result = word ; NEW_LINE length = len ( word ) ; NEW_LINE DEDENT DEDENT return result ; NEW_LINE DEDENT dict1 = [ " ale " , " apple " , " monkey " , " plea " ] ; NEW_LINE str1 = " abpcplea " ; NEW_LINE print ( findLongestString ( dict1 , str1 ) ) ; NEW_LINE