942. 增减字符串匹配

作者: 1江春水 | 来源:发表于2019-07-24 15:45 被阅读2次

【题目描述】

给定只含 "I"(增大)或 "D"(减小)的字符串 S ,令 N = S.length。
返回 [0, 1, ..., 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,4,1,3,2]

【示例2】

输出:"III"
输出:[0,1,2,3]

【示例3】

输出:"DDI"
输出:[3,2,0,1]

思路:
题意意思是 给你一个只包含I和D的字符串,然后返回同时满足一下条件的数组

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

  • 当字符为 I 时,返回所对应的数字是递增的;
  • 当字符为 D 时,返回所对应的数字是递减的;
  • 返回的数字区间是 0-S.length
  • 所以定义两个变量min(对应I) 和 max(对应D),min从0开始 来记录 I 所对应的数字,每碰到一个 I ,min++,max从S.length开始,每碰到一个D,max--
  • 时间复杂度为字符串的遍历 O(n)
  • 空间复杂度为O(n)
    代码实现:
func diStringMatch(_ S: String) -> [Int] {
    var result = [Int]()
    var min = 0
    var max = S.count
    for cha in S {
        if cha == "I" {
            result.append(min)
            min+=1
        } else {
            result.append(max)
            max-=1
        }
    }
    result.append(min)
    return result
}

相关文章

网友评论

    本文标题:942. 增减字符串匹配

    本文链接:https://www.haomeiwen.com/subject/piwxrctx.html