README.md

backtracking

We can decode patterns after match from tha pattern and the string. If the pattern already match then we need to check the string to see if the upcoming string matches the pattern. If we encounter a new pattern, then we need to try all the possibilities of subtring to match that new pattern.

pattern = abab
s = redblueredblue
                     ""
                    / \   \         \  \
                  r  re   red        .....
                          /   \   \
                  ...  red|b ...  red|blue ...
                  ... ...

For each level:

• the branches are matching all the possible matches with first char in pattern
• the height is the length of the pattern.

time: O(s^p) - s: length of string p: length of pattern
space: O(p)