Minimum Break

First of all, let's define a function checkCompatibility to check compatibility between two strings 'P' and 'Q' which takes 4 arguments the string 'P' the string 'Q', and 2 integer values ‘i’ and ‘j’  to keep track of the index of 'P' and 'Q' respectively.

The idea is pretty straightforward: iterate through 'P' and 'Q' while there is a match between the current character of 'P'  and the current character of 'Q'. If we reach the end of both strings while there is still a match, we will return 1 denoting that the strings are compatible, otherwise, we will return 0. The scan is done by having a pointer each in string 'P' and 'Q'.

Below is the detailed algorithm: 
 

1. Let ‘i’ denote the current index of string 'P' and ‘j’ denote the current index of 'Q'.
2. If ‘i’ = 'P'.length() and j = 'Q'.length() then return 1.
3. If ‘j’ = 'Q'.length()
   1. If 'P'[i] = ' * ' then call checkCompatibility ( 'P', 'Q', ‘i’ + 1 , ‘j’ )
   2. Else return 0.
4. If ‘i’ = 'P'.length () then return 0.
5. If 'P'[i] = ' * ' then we will return 1 if either  checkCompatibility ( 'P', 'Q', ‘i’ + 1 , ‘j’ ) or checkCompatibility ( 'P', 'Q', ‘i’  , ‘j’ + 1) returns 1, otherwise we will return 0.
6. If 'P'[i] = 'Q'[j] we will return checkCompatibility ( 'P', 'Q', ‘i’ + 1 , ‘j’ + 1) otherwise we will return 0.

Now we will iterate over the Array ‘ARR’ and call checkCompatibility ( ‘S’, ‘M’, 0, 0 ) for each of the array element ‘M’ and we will return 1 if we get 1 as output during any iteration. Otherwise we will return 0.

In the previous approach, the function checkCompatibility recursively checks the compatibility between two strings which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use Dynamic Programming to overcome the overlapping subproblems.

Note that the remaining work will be the same as the previous approach, we will just optimize the ‘checkCompatibility’ function using Dynamic Programming.

Steps:

1. Make a 2D array 'IS_COMPATIBLE' to store the DP states having 'P'.length()+1 rows and ‘Q’.length() +1 columns with all values initialized as 0. We will be using 1 - based indexing here.
2. 'IS_COMPATIBLE'[i][j] denotes whether the string formed by taking first ‘i’ characters of String 'P' is compatible with the string formed by taking first ‘j’ characters of string ‘Q’.
3. Set 'IS_COMPATIBLE'[0][0] = 1 as the base case.
4. Do a for loop for ‘i’ = 1 to 'P'.length()
   • Set 'IS_COMPATIBLE' [i][0] = 1 if 'P'[i]= ' *' , otherwise break.
5. Do a for loop for ‘i’ = 1 to 'P'.length()
   • Do a for loop for ‘j’ = 1 to ‘Q’.length()
     1. If 'P'[i] = ' * ' then set 'IS_COMPATIBLE'[i][j] as 1 if either  'IS_COMPATIBLE'[i][j-1] or 'IS_COMPATIBLE'[i-1][j]   is 1.
     2. Otherwise set 'IS_COMPATIBLE'[i][j] as 1 if and only if 'P'[i] = ‘Q’[j] and 'IS_COMPATIBLE' [i-1][j-1] = 1.
6. FInally return 'IS_COMPATIBLE'['P'.length()][‘Q’.length()], as this will denote whether strings 'P' and ‘Q’ are compatible or not.

The idea is to build an iterative approach to check compatibility between two strings. The benefit of an iterative approach is that only constant extra space will be used. We will use four-pointers ‘i’ pointing to String 'P', ‘j’ pointing to String Q, 'LAST_STAR_INDEX' to store the latest index of String 'P' at which the character is '*' and 'CORRESPONDING_INDEX' to store the corresponding Index of string 'Q' for that '*' character. The approach is to start comparing both the strings character by character and backtrack to the latest position containing '*' whenever a match is not found. In the end if we reach the end of both strings we will return 1 otherwise we will return 0.

Note that the remaining working will be the same as the first approach, we will just optimize the function ‘checkCompatibility’.

Below is the detailed algorithm:

1. Initialize ‘i’ = 0 , ‘j’ = 0, 'LAST_STAR_INDEX' = -1, 'CORRESPONDING_INDEX' = -1.
2. Do a while loop with terminating condition ( ‘j’ < 'Q'.length() )
   • If ( ‘i’ < 'P'.length() and 'P'[i] = 'Q'[j] ) then increase i by 1 and j by 1.
   • Else If ( i < 'P'.length() and  'P'[i] = '*' ) then set 'LAST_STAR_INDEX' = ‘i’, 'CORRESPONDING_INDEX' = ‘j’, and increment ‘i’ by 1.
   • Else if 'LAST_STAR_INDEX' = -1 then return 0.
   • Else we need to backtrack to the position where the last '*' character occurred in String 'P' as the current arrangement did not work. We also need to backtrack to the Corresponding Index in String 'Q'. So we will set ‘i’ = 'LAST_STAR_INDEX' +1, set ‘j’ = 'CORRESPONDING_INDEX' + 1 and increase 'CORRESPONDING_INDEX' by 1.
3. Do a while loop with terminating condition ( ‘i’ < 'P'.length() and 'P'[i] = '*' )
   • Increment ‘j’ by 1.

Return 1 if ‘j’ = 'P'.length() otherwise return 0.