Need Regular Expression for matching all permutations of a given word

Question

I am solving a problem where I need to match different case insensitive permutations of a given word in the target string.

For example :

word to match : cAda

target string : AbrAcadAbRa

Here, 2 possible permutations that can be found in the target string S are Acad and cadA.

I have written something like this :

    String pattern = "" ;

    for(char ch : word.toCharArray()){
        pattern = pattern + "(?=[\\s\\S]*(" + ch + "))" ;
    }
    pattern = "^" + pattern + "*$";

    Pattern r = Pattern.compile(pattern, Pattern.CASE_INSENSITIVE);

It does not work.

Regex is a very poor match for this task. If you want all permutations, the regex should contain all permutations, not a single word. — Sergey Kalinichenko, Apr 13 '17 at 13:10
can you show me how through some code, I am still learning regexp — Raghvendra Kumar, Apr 13 '17 at 13:12
@WiktorStribiżew: that was my initial idea, but that won't work since `aaaa` will also match: the character group contains an `[a...]{4}` so the permutation does not necessary takes all characters into account. — Willem Van Onsem, Apr 13 '17 at 13:13
Yes, but it is a good idea to show in comments that regex is not suitable here. — Wiktor Stribiżew, Apr 13 '17 at 13:15
Is it impossible to solve using regex or it will be a performance issue ? — Raghvendra Kumar, Apr 13 '17 at 13:17

score 0 · Answer 1 · answered Apr 13 '17 at 14:06

Regular expression is not the best tool for this task. You would have to generate a new regular expression for every input word. Not impossible, but overly complicated.

You'd be better off sorting the letters of the target word, then for each n-length substring of the input word, sort the letters and see if they match the sorted target word.

So, given the target word "cAda", you sort it to give "Aacd".

The user inputs "AbrAcadAbRa"

So you take the first 4-letter substring, "AbrA", sort it to get "AAbr", and check it against the sorted target. No match. Then take "brAc", sort it, and check. Then "Acad", etc.

There are some potential optimizations to avoid the sorting, but with small strings they probably don't matter very much.

Need Regular Expression for matching all permutations of a given word

1 Answers1