[Swift Weekly Contest 111]LeetCode942. 增减字符串匹配 | DI S

发布时间：2020-12-14 05:09:47 所属栏目：百科来源：网络整理

导读：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

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,3,2]

Example 2:

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

Example 3:

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

?Note:

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

给定只含?"I"（增大）或?"D"（减小）的字符串?S?，令?N = S.length。

返回?[0,N]?的任意排列?A?使得对于所有?i = 0,N-1，都有：

如果?S[i] == "I"，那么?A[i] < A[i+1]
如果?S[i] == "D"，那么?A[i] > A[i+1]

示例 1：

输出："IDID"
输出：[0,2]

示例 2：

输出："III"
输出：[0,3]

示例 3：

输出："DDI"
输出：[3,1]

提示：

1 <= S.length <= 1000
S?只包含字符?"I"?或?"D"。

2096ms

 1 class Solution {
 2     func diStringMatch(_ S: String) -> [Int] {
 3         var n:Int = S.count + 1
 4         var ret:[Int] = [Int](repeating: 0,count: n)
 5         var v:Int = n - 1
 6         var pre:Int = 0
 7         for i in 0..<(n - 1)
 8         {
 9             if S[i] == "D"
10             {
11                 for j in (pre...i).reversed()
12                 {
13                     ret[j] = v
14                     v -= 1
15                 }
16                 pre = i + 1
17             }
18         }
19         for j in (pre...(n - 1)).reversed()
20         {
21             ret[j] = v
22             v -= 1
23         }
24         return ret
25     }
26 }
27 
28 extension String {
29     //subscript函数可以检索数组中的值
30     //直接按照索引方式截取指定索引的字符
31     subscript (_ i: Int) -> Character {
32         //读取字符
33         get {return self[index(startIndex,offsetBy: i)]}
34     }
35 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!