[leetCode] 821. Shortest Distance to a Character (Python)

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.

첫번째 시도

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        S = S.replace(C, "0")
        
        s_list = list(S)
        
        before_idx = 0
        
        for i in range(len(s_list)):
            if s_list[i].isdigit():
                for j in range(before_idx, i):
                    s_list[j] = i - j
                before_idx = i + 1
                
        s_list = list(map(int, s_list))
        return s_list

첫번째 시도 - Example 1 결과

Example 1 결과 :  [3,2,1,0,1,0,0,4,3,2,1,0]
Example 1 정답 :  [3,2,1,0,1,0,0,1,2,2,1,0]

첫번째 시도는 먼저 대상 문자를 0으로 바꾼 후 단순하게 리스트를 돌면서 0이 나오면

해당 숫자 위치 앞에는 이전 0 또는 처음부터 0까지 그 사이의 길이만큼의 숫자에서 1까지

숫자를 하나씩 줄여가면서 넣어주도록 했습니다.

 

그리고 정답을 보니 문제의 제목부터 제대로 안읽어서 틀렸구나 라는 생각이 들었습니다.

 

두번째 시도

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        s_list = list(S)
        
        idx_list = []
        
        for i in range(len(s_list)):
            if s_list[i] == C:
                idx_list.append(i)
                
        
        answer_list = []
        
        for i in range(len(s_list)):
            temp = min([ abs(i-idx) for idx in idx_list ])
            
            answer_list.append(temp)
            
        return answer_list

이번에는 target 문자인 C의 위치를 미리 idx_list에 담아두고

S 의 길이만큼 반복문을 돌며 C의 위치들과 각 인덱스의 값의 거리가 가장 짧은 값들만 answer_list에 순서대로 담으면

정답이 완성됩니다.

SOMJANG/CODINGTEST_PRACTICE