Breaking Down Strategy

                    Breaking Down Big Problems 

   Some "big" problem looks very scary at the beginning. However, after we carefully analyze the problem, we may find that it is not the case, which simply because the "big" problem actually is composed by few relatively easy parts.  We could, therefore, solve them one by one. ^^ 

 Here is 3 examples that you may find out breaking down into sub-parts is very helpful to solve them. 

           Example 1: One Edit Distance 

Given two strings S and T, determine if they are both one edit distance apart.

Explain: two string is one distance apart when they only have one place be different. For example: "xyz" with "xy" ;   "abc" with "abd" ; " zero" with " fero". 

--------------------------------------------------------------------------------------------------------------------------

Analyze: There are lots of way to solving this problem. For example, you may use dynamic programming, or you may try to find first place they being different and made that change see if the resulting two string is the same. But, to me, the most straightforward  and clear solution is breaking down this problem in to two cases, which are deleting one character, or modifying one character. What's more, from the length of two input string we could easily find out which case we should put them into. ( if length are same, we consider one modifying case, else consider one deleting case). 

Here is  a solution based on the idea discussed above: 

           Example 2:  Regular Expression Matching 

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

--------------------------------------------------------------------------------------------------------------------------

Analyze: This is a very classic problem that many people do no know how to deal with at the beginning. But if we break down this problem into 3 sub-problems, you may find a relatively easy way to solve it.  

                                      1. There is "*" at next position. 

                                      2. There is "."  at next position. 

                                      3. There is a regular character at next position.   

  ---------------Now try it, see if you could solve it recursively based on those 3 cases ! -------------------

Here is a recursive solution: 

(Note that we reduce the input size every recursive call, until we reach the base case). 

Update( 7 / 23 / 2017 ) 
Recursive approach will cost up to O(4^m) time complexity where m is the length of the pattern. Here is the DP approach which only cost O(n*m), where n , m is the size of string and pattern ~. 

      Example 3: Wildcard Matching  

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Notice: The difference between Wildcard Matching and Regular Expression is not only about transform '?' to  '.' , but also '*' in Wildcard can exist independently mach any single or more sequence, while '*' in regular expression could only extend previous character. 

Analyze: Again, we could breaking down this problem into 3 sub-problems: 

                                                               1. if we get '*' in next position. 

                                                               2. if we get '?' 

                                                               3. or if we get  regular character 

--------------------------------------------------------------------------------------------------------------------

Here is a solution using two pinter to scan two string: 

Notice: Although there is detail explanation in the comment of above code, just want to mention that  if we meet '*' before, then (NIndex will != -1) so we can keep entering the case 3 in above code, which represent '*' can represent any single or more sequence in wildcard matching. 

Hope this idea to solve problem could help you ! 

Enjoy Coding^^ 

Ye Jiang