Решение: Кратчайшее расстояние до персонажа

Это часть серии пояснений к решению Leetcode ( index ). Если вам понравилось это решение или вы нашли его полезным, пожалуйста, поставьте лайк этому сообщению и/или проголосуйте мое решение опубликовано на форумах Leetcode

Проблема с кодом #821 (простая): Кратчайшее расстояние до символа

Описание:

Дана строка s и персонаж c это происходит в s , возвращает массив целых чисел ответ где где и ответ[я] является кратчайшим расстоянием от s[я] к персонажу c в s .

Примеры:

Ввод:
Выход:	[3,2,1,0,1,0,0,1,2,2,1,0]

Ввод:
Выход:	[3,2,1,0]

Ограничения:

1.длина^4
s[i] и c – строчные английские буквы.
c встречается по крайней мере один раз в s .

Идея:

Поскольку эта проблема требует, чтобы мы ссылались на символы как впереди, так и позади текущего символа, это должно напоминать двухпроходное динамическое программирование решение. Мы можем выполнить итерацию по входной строке ( S ) один раз и заполнить наш массив ответов ( и ) расстоянием от предшествующего вхождения C .

Затем мы можем выполнить итерацию в обратном направлении через S снова, чтобы мы могли выбрать наилучший результат между значением, которое мы получили в первом проходе, и расстоянием от предыдущего C движется в противоположном направлении.

Код Javascript:

Лучший результат для приведенного ниже кода – 80 мс/39,0 МБ (превышает 99%/100%).

var shortestToChar = function(S, C) {
    let len = S.length, ans = new Uint16Array(len)
    ans[0] = S.charAt(0) === C ? 0 : 10001
    for (let i = 1; i < len; i++) 
        ans[i] = S.charAt(i) === C ? 0 : ans[i-1] + 1
    for (let i = len - 2; ~i; i--)
        ans[i] = Math.min(ans[i], ans[i+1] + 1)
    return ans
};

Код Python3:

Лучший результат для приведенного ниже кода – 28 мс/14,3 МБ (превышает 99%/86%).

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        ans = []
        ans.append(0 if S[0] == C else 10001)
        for i in range(1,len(S)):
            ans.append(0 if S[i] == C else ans[i-1] + 1)
        for i in range(len(S)-2,-1,-1):
            ans[i] = min(ans[i], ans[i+1] + 1)
        return ans

Java-код:

Лучший результат для приведенного ниже кода – 1 мс/38,8МБ (превышает 97%/93%).

class Solution {
    public int[] shortestToChar(String S, char C) {
        int len = S.length();
        int[] ans = new int[len];
        ans[0] = S.charAt(0) == C ? 0 : 10001;
        for (int i = 1; i < len; i++) 
            ans[i] = S.charAt(i) == C ? 0 : ans[i-1] + 1;
        for (int i = len - 2; i >= 0; i--)
            ans[i] = Math.min(ans[i], ans[i+1] + 1);  
        return ans;
    }
}

Код на C++:

Наилучший результат для приведенного ниже кода – 0ms/6.5 мегабайт (превышает 100%/97%).

class Solution {
public:
    vector shortestToChar(string S, char C) {
        int len = S.length();
        std::vector ans;
        ans.push_back(S[0] == C ? 0 : 10001);
        for (int i = 1; i < len; i++) 
            ans.push_back(S[i] == C ? 0 : ans[i-1] + 1);
        for (int i = len - 2; i >= 0; i--)
            ans[i] = min(ans[i], ans[i+1] + 1);  
        return ans;
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-shortest-distance-to-a-character-ca9”

Проблема с кодом #821 (простая): Кратчайшее расстояние до символа

Читайте ещё по теме: