## Monday, August 8, 2016

### Google – Minimum Fluctuation Sequence

iii -> 1234
ddd -> 4321
iid -> 1243

[Solution]

[Note]

`class` `Solution {`
`  ``public` `int` `fluctuationSequence(String pattern) {`
`    ``if` `(pattern == ``null` `|| pattern.isEmpty()) {`
`      ``return` `0``;`
`    ``}`
`    `
`    ``List<Integer> list = ``new` `LinkedList<>();`
`    ``list.add(``1``);`
`    ``int` `next = ``2``;`
`    ``int` `idx = ``0``;`
`    ``boolean` `firstD = ``true``;`
`    ``for` `(``char` `c : pattern.toCharArray()) {`
`      ``if` `(c == ``'i'``) {`
`        ``list.add(next);`
`        ``idx = list.size() - ``1``;`
`      ``}`
`      ``else` `if` `(firstD) {`
`        ``list.add(``0``);`
`        ``firstD = ``false``;`
`        ``continue``;`
`      ``}`
`      ``else` `{`
`        ``list.add(idx, next);`
`      ``}`
`      ``next++;`
`    ``}`
`    `
`    ``int` `result = ``0``;`
`    ``for` `(``int` `num : list) {`
`      ``result = result * ``10` `+ num;`
`    ``}`
`    ``return` `result;`
`  ``}`
`}`

`// digit能重复, candy解法`
`class` `Solution2 {`
`  ``public` `int` `fluctuationSequence(String pattern) {`
`    ``if` `(pattern == ``null` `|| pattern.isEmpty()) {`
`      ``return` `0``;`
`    ``}`
`    `
`    ``int``[] nums = ``new` `int``[pattern.length() + ``1``];`
`    ``nums[``0``] = ``1``;`
`    ``int` `prev = ``1``;`
`    ``boolean` `firstD = ``true``;`
`    ``for` `(``int` `i = ``0``; i < pattern.length(); i++) {`
`      ``char` `c = pattern.charAt(i);`
`      ``if` `(c == ``'i'``) {`
`        ``nums[i + ``1``] = prev + ``1``;`
`        ``prev = prev + ``1``;`
`      ``}`
`      ``else` `if` `(firstD) {`
`        ``nums[i + ``1``] = ``0``;`
`        ``prev = ``0``;`
`        ``firstD = ``false``;`
`      ``}`
`      ``else` `if` `(prev == ``0``) {`
`        ``nums[i + ``1``] = ``0``;`
`      ``}`
`      ``else` `{`
`        ``nums[i + ``1``] = prev - ``1``;`
`        ``prev = prev - ``1``;`
`      ``}`
`    ``}`
`    `
`    ``for` `(``int` `i = pattern.length() - ``1``; i >= ``0``; i--) {`
`      ``char` `c = pattern.charAt(i);`
`      ``if` `(c == ``'i'` `&& nums[i] >= nums[i + ``1``]) {`
`        ``nums[i + ``1``] = nums[i] + ``1``;`
`      ``} `
`      ``else` `if` `(c == ``'d'` `&& nums[i] <= nums[i + ``1``]) {`
`        ``nums[i] = nums[i + ``1``] + ``1``;`
`      ``}`
`    ``}`
`    `
`    ``int` `result = ``0``;`
`    ``for` `(``int` `num : nums) {`
`      ``result = result * ``10` `+ num;`
`    ``}`
`    ``return` `result;`
`  ``}`
`}`