題目連結:

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
        }
    }