순열_LeetCode_permutation-in-string

https://leetcode.com/problems/permutation-in-string/submissions/

Permutation in String - LeetCode

 

문제 접근

1. s1의 순열을 Set으로 준비.

2. 준비된 Set의 element가 s2에 포함되었는지 확인.

실패 코드

실패 사유 : Time Limit Exceeded

개선 방법 : 순열 코드의 개선?

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        
        if s1 == s2 || s2.contains(s1) {
            return true
        }
        
        if s2.count < s1.count {
            return false
        }
        
        let set = doPermutation(input: s1, limit: s1.count, used: [], answer: "", answerArray: [])
        for item in set {
            if s2.contains(item) {
                return true
            }
        }
        
        return false
    }
    
    func doPermutation(input: String, limit: Int, used: [Int], answer: String, answerArray: Set<String>) -> Set<String> {
        var present = answer
        var presentArray = answerArray
        var presentUsed = used
        
        if present.count == limit {
            presentArray.insert(present)
            return presentArray
        }
        
        for index in 0..<limit {
            if used.contains(index) {
                continue
            }
            
            let stringIndex = input.index(input.startIndex, offsetBy: index)
            
            present.append(input[stringIndex])
            presentUsed.append(index)
            
            let result = doPermutation(input: input, limit: limit, used: presentUsed, answer: present, answerArray: presentArray)
            presentArray = presentArray.union(result)
            
            present.removeLast()
            presentUsed.removeLast()
        }
        
        return presentArray
        
    }
}