Google – Minimum Fluctuation Sequence

Google – Minimum Fluctuation Sequence
给一个String pattern, 包好两个字母i和d，i表示increase, d表示decrease, 生成一个最小的且满足pattern的数字，比如：
iii -> 1234
ddd -> 4321
iid -> 1243
每个数字不能重复使用。能重复使用的解法见后面follow up.
[Solution]
Greedy + Linked list
维护一个linked list来存每个digit，用一个pointer来指向最近一次碰到d的digit，一旦碰到i，pointer就指向tail.
[Note]
需要注意一下0这个特殊情况，因为第一个digit不能为0，所以pattern中第一个d肯定对应0。需要特殊处理一下。

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;

  }

}

Read full article from Google – Minimum Fluctuation Sequence