###### tags: `Leetcode` `easy` `array` `string` `python` `c++`

# 821. Shortest Distance to a Character

## [題目連結:] https://leetcode.com/problems/shortest-distance-to-a-character/description/

## 題目:
Given a string ```s``` and a character ```c``` that occurs in s, return an array of integers ```answer``` where ```answer.length == s.length``` and ```answer[i]``` is the **distance** from index ```i``` to the **closest** occurrence of character ```c``` in ```s```.

The **distance** between two indices ```i``` and ```j``` is ```abs(i - j)```, where ```abs``` is the absolute value function.

**Example 1:**

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

**Example 2:**

Input: s = "aaab", c = "b"
Output: [3,2,1,0]

## 解題想法:
* 題目為給一字符串s與一個在s中的字符c，求字符串中每個字符到最近的c的距離

* 遍歷數組:
* 先找出每个c出現的位置:
* 存於distance[]
* targetPos=0 #紀錄目前是使用distance中哪個位置的'c'
* 遍歷字符串(for pos in range(len(s))) 和c出現的位置，找到距離最近的c
* case1:
* pos<distance[0]: #比最左邊還小 直接與最左邊比較即可
* case2:
* pos>distance[-1]: #比最右邊大 直接比較最右邊即可
* case3:
* pos==distance[targetPos]: #當前遍歷到的位置的值為c
* res.append(0)
* targetPos+=1
* case4:
* 比較與左右邊哪邊絕對值較小
* min(abs(distance[targetPos]-pos),abs(distance[targetPos-1]-pos))

## Python:

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        res=[]
        distance=[]
        for pos,val in enumerate(s):
            if val==c:
                distance.append(pos)
        targetPos=0 #紀錄目前是使用distance中哪個位置的'c'
        for pos in range(len(s)):
            if pos<distance[0]: #比最左邊還小 直接與最左邊比較即可
                res.append(distance[0]-pos)
            elif pos>distance[-1]: #比最右邊大 直接比較最右邊即可
                res.append(pos-distance[-1])
            elif pos==distance[targetPos]:
                res.append(0)
                targetPos+=1
            else: #比較與左右邊哪邊絕對值較小
                res.append(min(abs(distance[targetPos]-pos),abs(distance[targetPos-1]-pos)))
        return res

## C++:

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> res, distance;
        for (int i=0; i<s.size(); i++){
            if (s[i]==c)
                distance.push_back(i);
        }
        int d=distance.size();
        int targetPos=0;
        for (int i=0; i<s.size(); i++){
            if (i<distance[0])
                res.push_back(distance[0]-i);
            else if (i>distance[d-1])
                res.push_back(i-distance[d-1]);
            else if (i==distance[targetPos]){
                res.push_back(0);
                targetPos+=1;
            }
            else{
                res.push_back(min(distance[targetPos]-i, i-distance[targetPos-1]));
            }
        }
        return res;
    }
};