[LeetCode]942. DI String Match

发表于 | 分类于 | 评论数： | 阅读次数：
字数统计：360 字 | 阅读时长：2 分钟

942. DI String Match

Easy

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:

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

Example 2:

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

Example 3:

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

Note:

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

方案一

思路：返回的vector大小比S大 1，最大值即为S.size()，最小值为0，遇到I，最小值加1，遇到D，最大值减1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> diStringMatch(string S) {
        int min = 0;
        int max = S.size();
        vector<int> out;
        for (char c : S) {
            if (c == 'I') {
                out.push_back(min++);
            } else {
                out.push_back(max--);
            }
        }
        out.push_back(min);
        return out;
    }
};

result

Runtime: 56 ms, faster than 8.41% of C++ online submissions for DI String Match.

Memory Usage: 10.3 MB, less than 56.84% of C++ online submissions for DI String Match.

方案二

思路差不多，使用case代替if，初始化vector指定长度；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> diStringMatch(string S) {
        int min = 0;
        int max = S.size();
        int len = max;
        vector<int> out(len+1, 0);
        for (int i = 0; i < len; i++) {
            switch(S[i]) {
            case 'I':
                out[i] = min++;
                break;
            case 'D':
                out[i] = max--;
                break;
            }
        }
        out[len] = max;
        return out;
    }
};

result

Runtime: 36 ms, faster than 97.85% of C++ online submissions for DI String Match.

Memory Usage: 9.8 MB, less than 95.04% of C++ online submissions for DI String Match.