# LeetCode – 942. DI String Match

### 題目連結:

https://leetcode.com/problems/di-string-match/

### 參考解法:

https://leetcode.com/problems/di-string-match/discuss/755754/Swift-Simple-Solution

### 法ㄧ(Time complexity: O(n), Space complexity: O(n) note: s is the length of s)

``````    func diStringMatch(_ s: String) -> [Int] {
guard s.count > 0 else { return [] }
let sArr = Array(s)
var arr = Array(repeating: 0, count: s.count)
var low = 0
var high = s.count
var index = 0
for c in s {
if c == "D" {
arr[index] = high
high -= 1
} else {
arr[index] = low
low += 1
}
index += 1
}
arr.append(high) // note: arr.append(low) also works
return arr
}``````

### 延伸題（印出所有可能的permutation):

``````    func diStringMatch(_ s: String) -> [[Int]] {
guard s.count > 0 else { return [] }
let sArr = Array(s)
var arr = Array(repeating: 0, count: s.count + 1)
for i in 0 ..< arr.count {
arr[i] = i
}

var result: [[Int]] = []
helper(arr, sArr, &result, 0, [])
return result
}

func helper(_ arr: [Int], _ sArr: [Character] ,_ result: inout [[Int]], _ curStep: Int, _ curPerm: [Int]) {
if curPerm.count == sArr.count + 1 {
result.append(curPerm)
return
}

var tmpArr = arr
for i in 0 ..< tmpArr.count {
let val = tmpArr.remove(at: i)
if curStep == 0 || isValidNum(curPerm.last, val, sArr[curStep - 1]) {
helper(tmpArr, sArr, &result, curStep + 1, curPerm + [val])
}
tmpArr.insert(val, at: i)
}
}

func isValidNum(_ a: Int?, _ b: Int, _ op: Character) -> Bool {
guard let a = a else { return true }
if op == "D" {
return a > b
} else {
return a < b
}
}``````