php challenge: parse pseudo-regex

Question

I have a challenge that I have not been able to figure out, but it seems like it could be fun and relatively easy for someone who thinks in algorithms...

If my search term has a "?" character in it, it means that it should not care if the preceding character is there (as in regex). But I want my program to print out all the possible results.

A few examples: "tab?le" should print out "table" and "tale". The number of results is always 2 to the power of the number of question marks. As another example: "carn?ati?on" should print out:

• caraton
• caration
• carnaton
• carnation

I'm looking for a function that will take in the word with the question marks and output an array with all the results...

Answer 1

Following your example of "carn?ati?on":

You can split the word/string into an array on "?" then the last character of each string in the array will be the optional character:

[0] => carn
[1] => ati
[2] => on

You can then create the two separate possibilities (ie. with and without that last character) for each element in the first array and map these permutations to another array. Note the last element should be ignored for the above transformation since it doesn't apply. I would make it of the form:

[0] => [carn, car]
[1] => [ati, at]
[2] => [on]

Then I would iterate over each element in the sub arrays to compute all the different combinations.

If you get stuck in applying this process just post a comment.