76. Minimum Window Substring

LeetCode hard original: C# #array #csharp #hard #hash-table #leetcode #sliding-window #string #tree #two-pointers

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

LeetCode Static

given две строки s и t длиной m и n соответственно. return наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) 入力ил в эту подстроку. Если такой подстроки не существует, return пустую строку "".

Тестовые 例ы будут сформированы таким образом, что ответ будет уникальным.

例:

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

C# 解法

照合済み/オリジナル

public class Solution {
    public string MinWindow(string s, string t) {
        if (s.Length == 0 || t.Length == 0) {
            return "";
        }
        Dictionary<char, int> dictT = new Dictionary<char, int>();
        for (int i = 0; i < t.Length; i++) {
            if (dictT.ContainsKey(t[i])) {
                dictT[t[i]]++;
            } else {
                dictT[t[i]] = 1;
            }
        }
        int required = dictT.Count;
        int l = 0, r = 0;
        int formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        int[] ans = { -1, 0, 0 };
        while (r < s.Length) {
            char c = s[r];
            if (windowCounts.ContainsKey(c)) {
                windowCounts[c]++;
            } else {
                windowCounts[c] = 1;
            }
            if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }
            while (l <= r && formed == required) {
                c = s[l];
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts[c]--;
                if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1] + 1);
    }
}

C++ 解法

自動ドラフト、提出前に確認

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string MinWindow(string s, string t) {
        if (s.size() == 0 || t.size() == 0) {
            return "";
        }
        unordered_map<char, int> dictT = new unordered_map<char, int>();
        for (int i = 0; i < t.size(); i++) {
            if (dictT.count(t[i])) {
                dictT[t[i]]++;
            } else {
                dictT[t[i]] = 1;
            }
        }
        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;
        unordered_map<char, int> windowCounts = new unordered_map<char, int>();
        vector<int>& ans = { -1, 0, 0 };
        while (r < s.size()) {
            char c = s[r];
            if (windowCounts.count(c)) {
                windowCounts[c]++;
            } else {
                windowCounts[c] = 1;
            }
            if (dictT.count(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }
            while (l <= r && formed == required) {
                c = s[l];
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts[c]--;
                if (dictT.count(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1] + 1);
    }
}

Java 解法

照合済み/オリジナル

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }

        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
        int[] ans = { -1, 0, 0 };

        while (r < s.length()) {
            char c = s.charAt(r);
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);

            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s.charAt(l);
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

JavaScript 解法

照合済み/オリジナル

var minWindow = function (s, t) {
    if (s.length === 0 || t.length === 0) {
        return "";
    }
    let dictT = new Map();
    for (let i = 0; i < t.length; i++) {
        let count = dictT.get(t.charAt(i)) || 0;
        dictT.set(t.charAt(i), count + 1);
    }
    let required = dictT.size;
    let l = 0,
        r = 0;
    let formed = 0;
    let windowCounts = new Map();
    let ans = [-1, 0, 0];
    while (r < s.length) {
        let c = s.charAt(r);
        let count = windowCounts.get(c) || 0;
        windowCounts.set(c, count + 1);
        if (dictT.has(c) && windowCounts.get(c) === dictT.get(c)) {
            formed++;
        }
        while (l <= r && formed === required) {
            c = s.charAt(l);
            if (ans[0] === -1 || r - l + 1 < ans[0]) {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            windowCounts.set(c, windowCounts.get(c) - 1);
            if (dictT.has(c) && windowCounts.get(c) < dictT.get(c)) {
                formed--;
            }
            l++;
        }
        r++;
    }
    return ans[0] === -1 ? "" : s.substring(ans[1], ans[2] + 1);
};

Python 解法

照合済み/オリジナル

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        dict_t = Counter(t)
        required = len(dict_t)
        l, r = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None

        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                l += 1

            r += 1
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

Go 解法

照合済み/オリジナル

func minWindow(s string, t string) string {
    if len(s) == 0 || len(t) == 0 {
        return ""
    }
    dictT := make(map[rune]int)
    for _, c := range t {
        dictT[c]++
    }
    required := len(dictT)
    l, r := 0, 0
    formed := 0
    windowCounts := make(map[rune]int)
    ans := []int{-1, 0, 0}
    for r < len(s) {
        c := rune(s[r])
        windowCounts[c]++
        if _, ok := dictT[c]; ok && windowCounts[c] == dictT[c] {
            formed++
        }
        for l <= r && formed == required {
            c = rune(s[l])
            if ans[0] == -1 || r-l+1 < ans[0] {
                ans[0] = r - l + 1
                ans[1] = l
                ans[2] = r
            }
            windowCounts[c]--
            if _, ok := dictT[c]; ok && windowCounts[c] < dictT[c] {
                formed--
            }
            l++
        }
        r++
    }
    if ans[0] == -1 {
        return ""
    }
    return s[ans[1] : ans[2]+1]
}

Algorithm

1️⃣

Мы начинаем с двух указателей, left и right, которые изначально указывают на первый element строки S.

2️⃣

Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3️⃣

Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。