資訊專(zhuān)欄INFORMATION COLUMN
Problem
Given a string source and a string target, find the minimum window in source which will contain all the characters in target.
NoticeIf there is no such window in source that covers all characters in target, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.
ClarificationShould the characters in minimum window has the same order in target?
Not necessary.
ExampleFor source = "ADOBECODEBANC", target = "ABC", the minimum window is "BANC"
ChallengeCan you do it in time complexity O(n) ?
Solutionpublic class Solution {
public String minWindow(String source, String target) {
int[] S = new int[255], T = new int[255];
for (int i = 0; i < target.length(); i++) T[target.charAt(i)]++;
int start = 0, left = -1, right = source.length(), match = 0, len = source.length();
for (int i = 0; i < source.length(); i++) {
S[source.charAt(i)]++;
if (S[source.charAt(i)] <= T[source.charAt(i)]) match++;
if (match == target.length()) {
while (start < i && S[source.charAt(start)] > T[source.charAt(start)]) {
S[source.charAt(start)]--;
start++;
}
if (i - start < len) {
len = i - start;
left = start;
right = i;
}
S[source.charAt(start)]--;
match--;
start++;
}
}
return left == -1 ? "" : source.substring(left, right+1);
}
}
Solution: Updated 2018-10
class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
int[] dict = new int[256];
for (char ch: t.toCharArray()) {
dict[ch]++;
}
int l = 0, r = 0, start = -1;
int count = t.length();
int min = Integer.MAX_VALUE;
while (r < s.length()) {
char ch = s.charAt(r);
if (dict[ch] > 0) count--;
dict[ch]--;
r++;
while (count == 0) {
ch = s.charAt(l);
if (dict[ch] == 0) count++;
dict[ch]++;
if (r-l < min) {
min = r-l;
start = l;
}
l++;
}
}
return start == -1 ? "" : s.substring(start, start+min);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65972.html
摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。這里有一種情況是上述后三個(gè)，中點(diǎn)值和末位相等。此時(shí)，兩邊同時(shí)遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說(shuō)明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...
摘要：遍歷整個(gè)矩陣，對(duì)于，取上方和左邊較小值，與相加可得該點(diǎn)最小值。 Problem Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You ...
摘要：是左閉右開(kāi)區(qū)間，所以要。，要理解是和之間只有一個(gè)元素。循環(huán)每次的時(shí)候，都要更新子串更大的情況。補(bǔ)一種中點(diǎn)延展的方法循環(huán)字符串的每個(gè)字符，以該字符為中心，若兩邊為回文，則向兩邊繼續(xù)延展。循環(huán)返回長(zhǎng)度最長(zhǎng)的回文串即可。 Problem Given a string S, find the longest palindromic substring in S. You may assume ...
摘要：第一個(gè)分割點(diǎn)第二個(gè)分割點(diǎn)第三個(gè)分割點(diǎn) Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....
摘要：首先將兩個(gè)字符串化成字符數(shù)組，排序后逐位比較，確定它們等長(zhǎng)且具有相同數(shù)量的相同字符。然后，從第一個(gè)字符開(kāi)始向后遍歷，判斷和中以這個(gè)坐標(biāo)為中點(diǎn)的左右兩個(gè)子字符串是否滿(mǎn)足第一步中互為的條件設(shè)分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...
閱讀 2573·2023-04-25 18:13
閱讀 797·2021-11-22 12:10
閱讀 2989·2021-11-22 11:57
閱讀 2150·2021-11-19 11:26
閱讀 2185·2021-09-22 15:40
閱讀 1475·2021-09-03 10:28
閱讀 2714·2019-08-30 15:53
閱讀 1960·2019-08-30 15:44
