The DI (Decreasing/Increasing) String Match Algorithm

json-data

Your task is to return an array (that contains integer numbers from 0 to N, N is the length of a given string S that contains only I or D – denoting Increasing or Decreasing sequence) that satisfies for all i = 0 to i = N – 1.

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 <= S.length <= 10000
S only contains characters “I” or “D”.

The return array is size of N+1 (containing the numbers from 0 to N), if the first string character is I – then we can safely put 0 in the return permutation array – otherwise, we can safely put N at the beginning.

We define two number indicators at both end, moving towards each other, at the end, they will meet in the middle where low = high, and we just need to set this number to the last element in the return permutation. The Java implementation of such string match algorithm is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int[] diStringMatch(String S) {
        int sz = S.length();
        int lo = 0;
        int hi = sz;
        int[] r = new int[sz + 1];
        for (int i = 0; i < sz; ++ i) {
            if (S.charAt(i) == 'I') {
                r[i] = lo ++;
            } else {
                r[i] = hi --;
            }
        }
        r[sz] = lo; 
        return r;
    }
}

class Solution {
    public int[] diStringMatch(String S) {
        int sz = S.length();
        int lo = 0;
        int hi = sz;
        int[] r = new int[sz + 1];
        for (int i = 0; i < sz; ++ i) {
            if (S.charAt(i) == 'I') {
                r[i] = lo ++;
            } else {
                r[i] = hi --;
            }
        }
        r[sz] = lo; 
        return r;
    }
}

O(N) runtime complexity as well as the space complexity – and the below C++ uses the STL::vector container – but the idea is the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> diStringMatch(string S) {
        vector<int> r(S.size() + 1);
        int lo = 0, hi = S.size();
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == 'I') {
                r[i] = lo ++;
            } else {
                r[i] = hi --;
            }
        }
        r[S.size()] = hi;
        return r;
    }
};

class Solution {
public:
    vector<int> diStringMatch(string S) {
        vector<int> r(S.size() + 1);
        int lo = 0, hi = S.size();
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == 'I') {
                r[i] = lo ++;
            } else {
                r[i] = hi --;
            }
        }
        r[S.size()] = hi;
        return r;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —