Leetcode: DI String Match

DI String Match



Similar Problems:


Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length.

Return any permutation A of [0, 1, …, N] such that for all i = 0, …, N-1:

If S[i] = "I", then A[i] < A[i+1]
If S[i] =
“D”, then A[i] > A[i+1]

Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

Note:

  1. 1 <= S.length <= 10000
  2. S only contains characters “I” or “D”.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/di-string-match
// Basic Ideas: two pointers
// Complexity: Time O(n), Space O(1)
func diStringMatch(S string) []int {
    res := []int{}
    i, j := 0, len(S)
    for _, ch := range S {
        if ch == 'I' {
            res = append(res, i)
            i++
        } else {
            res = append(res, j)
            j--
        }
    }
    res = append(res, i)
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.