An interesting question however is: could your non-greedy idea work in general? Consider the case where
pattern = *X*X
input = AXBXCZ
According to the algorithm you described, the first * would match A (the substring until the first X in input). Then the second * would match B (the substring from the previous position to the next X). So we've gone through the entire pattern without encountering any mismatches. Does that mean we can return with "success"? Clearly, *X*X doesn't match AXBXCZ.
Yes it went through the wildcard search text but the pointer in the text that should match didn't reach the end so that indicates then no match.
A solution for a * at the start, which is indeed something overlooked, might be chosing the loop direction in the wildcard search string.
- If it starts with a *, loop from the end till the beginning and decrease the text pointer of course.
- If it ends with a *, loop from beginning till end and increase, as in the original example.
- If both beginning and ending *, perform both.
