LeetCode821. Shortest Distance to a Character

1. 문제(원본)

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e' Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

 

Note:

1. S string length is in [1, 10000].
2. C is a single character, and guaranteed to be in string S.
3. All letters in S and C are lowercase.

2. 문제

입력받은 문자열에서 찾고자 하는 입력 문자의 각 인덱스 별 거리의 최솟값을 배열로 반환하여라

3. 나의 답

class Solution {

    func shortestToChar(_ S: String, _ C: Character) -> [Int] {

        var result: [Int] = []

        var select: [Int] = []

        for index in 0..<S.count where S[S.index(S.startIndex, offsetBy: index)] == C {

            select.append(index)

        }

        for index in 0..<S.count {

            var least = S.count

            for input in select {

                least = min(abs(index - input), least)

            }

            result.append(least)

        }

        print(result)

        return result

    }

}

4. 다른 유저의 답

#1

class Solution {

    func shortestToChar(_ S: String, _ C: Character) -> [Int] {

       var res = Array(repeating: 0, count: S.count)

       let n = S.count

       var pos = -n

 

       for i in 0..<n {

           let index = S.index(S.startIndex, offsetBy: i)

           if S[index] == C {

               pos = i

           }

           res[i] = i - pos

       }

 

        for i in (0..<n).reversed() {

            let index = S.index(S.startIndex, offsetBy: i)

            if S[index] == C {

                pos  = i

            }

            res[i] = min(res[i], abs(pos - i))

        }

 

        return res

    }

}

5. 마무리

문제를 풀면서 로직을 구상할 때 최소 배열을 3개 정도는 써야한다고 생각했었는데 막상 문제를 풀고 다른 유저들의 답을 보면서 2개로도 충분히 구현이 가능한 것을 알았다. 역시 반복문이 3개보다는 2개인 쪽이 처리 속도가 더 빨랐다. 

이번 문제도 좋은 공부가 되는 것 같다.