What I came up with:
1) Creating a "normalized" string by removing slashes and numbers from the pattern. For example, "V/2ict/2or/3ia/11" turns into "Victoria".
2) Creating a map where keys are indexes of characters in the "normalized" string, but only of those characters that are dublicated as indicated in the pattern. Values are the amounts of dublicates of one such character. So the map for the example above:
{key 0 <=> value 2, key 3 <=> value 2, key 5 <=> value 3, key 7 <=> value 11}.
Keys are indexes in "Victoria", values are amounts of dublicates in "V/2ict/2or/3ia/11" (that is, maximum amounts of possible dublicates, according to your task)
3) Checking every possible combination of such dublicates. For example, I may fix 'V', then fix 't', then 'r', then 'a', and then compare the result "Victoria" with the username provided. If the strings are not equal, I may check "Victoriaa", then "Victoriaaa", and so on, until the strings are equal or the limit of allowed 'a' characters is exceeded. Then I, for example, fix 'rr", get "Victorria", and check all the other amounts of 'a' characters again. If the 'r'-limit is exceeded too and the strings are still not equal, I proceed to the next group of dublicated letters, and so on.
Since we don't know the exact amount of groups of dublicates, the solution requires recursion. If your task implies that there is only one such group in the username, the problem is MUCH easier. However, in general case, here's what I have.
This method iterates through the pattern string. It fills the map with values (substrings-numbers after slashes) and keys (indexes of elements that may be dublicated - indexes in the "normalized" string that is being created in the loop as well).
public static boolean verify(String name, String ptrn) { StringBuilder normalized = new StringBuilder(ptrn); int normalizingShift = 0; Map<Integer, Integer> allowedAppendices = new HashMap<>(); for (int i = 0; i < ptrn.length(); i++) { if (ptrn.charAt(i) == '/') { int j = i+1; while (j!=ptrn.length() && Character.isDigit(ptrn.charAt(j))) { j++; } normalized.delete(i - normalizingShift,j - normalizingShift); allowedAppendices.put(i - normalizingShift - 1, Integer.parseInt(ptrn.substring(i+1, j))); normalizingShift += j - i; } } return find(name, normalized, allowedAppendices, normalized.toString(), 0); }
Method find(..) has 5 arguments:
1) Provided username (isn't changed along the recursions, used only for comparison).
2) "Normalized" string as a StringBuilder object (a starting point for inserting).
3) The map, described above.
4) Immutable instance of "normalized" string, used only to get a right character for insertion.
5) Offset. (as we insert characters, we cannot rely on the indexing of initial "normalized" string).
At first, some map entry is randomly chosen. Then a reduced map is created by removing this entry. As I said, the map represents the group of dublicated characters, so going "deeper" we narrow the scope of available groups (for example, with first consider 'r' group, then 't' or 'V', etc). Then the copy of the StringBuilder "normalized" string is created (sb0). "entry.getValue()" returns the maximum amount of allowed dublicates of character "original.charAt(entry.getKey())". After the insertion we compare the result with the provided username. If the strings are different, we proceed to the next level of recursion, with reduced map, updated "active" string and increased offset. Username ("name") and initial normalized string ("original") are always untouched.
When the map is finally empty, we stop the recursion, iterate through all possible combinations with all letter groups fixed except for the one group under iteration. When the iteration is over, we return to the "upper" level of recursions, and the proccess repeats until the equality, or "return false;" line in the end.
public static boolean find(String name, StringBuilder sb, Map<Integer, Integer> map, String original, int offset) { Map.Entry<Integer,Integer> entry = map.entrySet().iterator().next(); Map<Integer,Integer> reducedMap = new HashMap<>(map); reducedMap.remove(entry.getKey()); StringBuilder sb0 = new StringBuilder(sb); for (int i = -1; i < entry.getValue(); i++) { if (i != -1) { sb0.insert(entry.getKey()+1+offset, original.charAt(entry.getKey())); offset++; } //System.out.println(sb0); if (name.equals(sb0.toString())) { return true; } if (!reducedMap.isEmpty()) { if (find (name, sb0, reducedMap, original, offset)) return true; } } return false; }
You can uncomment "System.out.println(sb0);" to see all the combinations the method goes through before finding the appropriate string (if any).
The iteration starts with -1 to include cases with zero letters added.
My tests:
public static void main(String[] args) { System.out.println(verify("VVVicttttorrria","V/2ict/2or/3ia")); System.out.println(verify("Victtorrria","V/2ict/2or/3ia")); System.out.println(verify("VVVicttttoia","V/2ict/2or/3ia")); System.out.println(verify("Victorrrria","V/2ict/22or/3ia")); System.out.println(verify("Victorrrriaaaaa","V/2ict/2or/3ia/11")); }