- Notifications
You must be signed in to change notification settings - Fork 33
Expand file tree
/
Copy pathConstructSmallestNumberFromDIString.java
More file actions
Latest commit
37 lines (33 loc) · 1.31 KB
/
Copy pathConstructSmallestNumberFromDIString.java
File metadata and controls
37 lines (33 loc) · 1.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
classSolution {
publicStringsmallestNumber(Stringpattern) {
intn = pattern.length();
boolean[] used = newboolean[10];
StringBuilderresult = newStringBuilder();
backtrack(pattern, 0, newint[n + 1], used, result);
returnresult.toString();
}
// !N
privatebooleanbacktrack(Stringpattern, intindex, int[] num, boolean[] used, StringBuilderresult) {
if (index > pattern.length()) {
for (inti = 0; i < num.length; i++) {
result.append(num[i]);
}
returntrue; // Found the valid lexicographically smallest number
}
for (intdigit = 1; digit <= 9; digit++) {
if (!used[digit] && (index == 0 || isValid(num[index - 1], digit, pattern.charAt(index - 1)))) {
used[digit] = true;
num[index] = digit;
if (backtrack(pattern, index + 1, num, used, result)) {
returntrue;
}
num[index] = 0;
used[digit] = false; // Backtrack
}
}
returnfalse;
}
privatebooleanisValid(intlastDigit, intcurrentDigit, charcondition) {
return (condition == 'I' && lastDigit < currentDigit) || (condition == 'D' && lastDigit > currentDigit);
}
}