Shortest Uncommon Subsequence | A dynamic programming based PHP program to find shortest uncommon subsequence . ; Returns length of shortest common subsequence ; declaring 2D array of m + 1 rows and n + 1 columns dynamically ; T string is empty ; S string is empty ; char not present in T ; Driver Code
< ? php $ GLOBALS [ ' MAX ' ] = 1005 ; function shortestSeq ( $ S , $ T ) { $ m = strlen ( $ S ) ; $ n = strlen ( $ T ) ; $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ m ; $ i ++ ) $ dp [ $ i ] [ 0 ] = 1 ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) $ dp [ 0 ] [ $ i ] = $ GLOBALS [ ' MAX ' ] ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { $ ch = $ S [ $ i - 1 ] ; for ( $ k = $ j - 1 ; $ k >= 0 ; $ k -- ) if ( $ T [ $ k ] == $ ch ) break ; if ( $ k == -1 ) $ dp [ $ i ] [ $ j ] = 1 ; else $ dp [ $ i ] [ $ j ] = min ( $ dp [ $ i - 1 ] [ $ j ] , $ dp [ $ i - 1 ] [ $ k ] + 1 ) ; } } $ ans = $ dp [ $ m ] [ $ n ] ; if ( $ ans >= $ GLOBALS [ ' MAX ' ] ) $ ans = -1 ; return $ ans ; } $ S = " babab " ; $ T = " babba " ; $ m = strlen ( $ S ) ; $ n = strlen ( $ T ) ; echo " Length ▁ of ▁ shortest ▁ subsequence ▁ is ▁ : ▁ " , shortestSeq ( $ S , $ T ) ; ? >