| 10 | |
| 11 | // !N |
| 12 | private boolean backtrack(String pattern, int index, int[] num, boolean[] used, StringBuilder result) { |
| 13 | if (index > pattern.length()) { |
| 14 | for (int i = 0; i < num.length; i++) { |
| 15 | result.append(num[i]); |
| 16 | } |
| 17 | return true; // Found the valid lexicographically smallest number |
| 18 | } |
| 19 | |
| 20 | for (int digit = 1; digit <= 9; digit++) { |
| 21 | if (!used[digit] && (index == 0 || isValid(num[index - 1], digit, pattern.charAt(index - 1)))) { |
| 22 | used[digit] = true; |
| 23 | num[index] = digit; |
| 24 | if (backtrack(pattern, index + 1, num, used, result)) { |
| 25 | return true; |
| 26 | } |
| 27 | num[index] = 0; |
| 28 | used[digit] = false; // Backtrack |
| 29 | } |
| 30 | } |
| 31 | return false; |
| 32 | } |
| 33 | |
| 34 | private boolean isValid(int lastDigit, int currentDigit, char condition) { |
| 35 | return (condition == 'I' && lastDigit < currentDigit) || (condition == 'D' && lastDigit > currentDigit); |