Problem Statement:
Given two strings a,b of length m and n (1<=m,n<=1000) which only contains 'A' and 'B' letters, there are k<=100 queries.
For each query: Given string S of length m+n, check if this string can be form by string a,b by keeping their original order.
(let's a = {x0,x1,x2,...,xm} , b = {y0,y1,y2,....,yn} ; S may be {x0,x1,y0,x2,y1,y2,x3,...} or something like this : position of x0<x1<x2<...<xm and position of y0<y1<y2<...<yn)
More formally: string a and b must be subsequence of string S which doesn't use the same postition of S twice.
For example:
let a = "BAB" , b = "AB" ==> Posible string S is "BAABB" ,"BABAB", "ABBAB" but not "BBABA"
how to solve this problem? I think it's dynamic programming problem. Thank you very much in advance.
I think $$$O(mnk)$$$ should pass. Let
dp[i][j]denote whether it's possible to make the first $$$i+j$$$ characters of $$$S$$$ using $$$i$$$ characters from $$$A$$$ and $$$j$$$ characters from $$$B$$$.dp[i][j] = (if a[i-1]==s[i+j-1] then dp[i-1][j] else 0) or (if b[j-1]==s[i+j-1] then dp[i][j-1] else 0). Obviously some other conditions such asdp[0][0]=1anddp[i][0] is dp[i-1][0] && s[i-1]==a[i-1]and the same thing fordp[0][j].