## Monday, August 8, 2016

Input一个string表示一个number, number不允许有重复的digit，返回满足要求的next number.

[Solution]
Next Permutation的升级版。

• break之后从break的位置开始用first missing number的方法generate后面的digit
• 如果扫到头都没有break，比如987就会是这样的情况，那就说明需要进一位。那么这种情况就是从头开始，generate一个n + 1位的number。
`  ``public` `String nextNumber(String num) {`
`    ``if` `(num == ``null` `|| num.isEmpty()) {`
`      ``return` `num;`
`    ``}`

`    ``int` `n = num.length();`
`    ``int``[] map = ``new` `int``[``10``];`
`    ``for` `(``char` `c : num.toCharArray()) {`
`      ``map[c - ``'0'``] = ``1``;`
`    ``}`

`    ``int` `i = ``0``;`
`    ``int` `next = -``1``;`
`    ``for` `(i = n - ``1``; i >= ``0``; i--) {`
`      ``int` `curr = num.charAt(i) - ``'0'``;`
`      ``next = curr + ``1``;`
`      ``while` `(next <= ``9` `&& map[next] == ``1``) {`
`        ``next++;`
`      ``}`
`      ``map[curr] = ``0``;`
`      ``if` `(next <= ``9``) {`
`        ``break``;`
`      ``}`
`    ``}`

`    ``StringBuilder sb = ``new` `StringBuilder();`
`    ``// 987 -> 1023`
`    ``if` `(i == -``1``) {`
`      ``sb.append(``"10"``);`
`      ``int` `d = ``2``;`
`      ``while` `(sb.length() < n + ``1``) {`
`        ``sb.append(d++);`
`      ``}`
`    ``}`
`    ``else` `{`
`      ``sb.append(num.substring(``0``, i));`
`      ``sb.append(next);`
`      ``map[next] = ``1``;`
`      ``next = ``0``;`
`      ``while` `(sb.length() < n) {`
`        ``while` `(next <= ``9` `&& map[next] == ``1``) {`
`          ``next++;`
`        ``}`
`        ``sb.append(next);`
`        ``map[next] = ``1``;`
`      ``}`
`    ``}`

`    ``return` `sb.toString();`
`  ``}`