输入包括两行,第一行一个字符串,代表str1,第二行也是一个字符串,代表str2。
输出str1的字串中含有str2所有字符的最小字符串长度,如果不存在请输出0。
abcde ac
3
“abc”中包含“ac”,且“abc”是所有满足条件中最小的。
12345 344
0
#include <stdio.h> #include <string.h> #include <limits.h> #define MIN(X, Y) ((X) < (Y) ? (X) : (Y)) #define MAX_LEN 100001 int min_len(char *str1, char *str2); int main(void) { char str1[MAX_LEN], str2[MAX_LEN]; scanf("%s%s", str1, str2); printf("%d\n", min_len(str1, str2)); return 0; } int min_len(char *str1, char *str2) { int len1 = (int) strlen(str1); int len2 = (int) strlen(str2); int map[256]; memset(map, 0, sizeof(int) * 256); for (int i = 0; i < len2; i++) { map[str2[i]]++; } int min_len = INT_MAX, need = len2; int l = 0, r = -1; while (++r < len1) { map[str1[r]]--; if (map[str1[r]] >= 0) need--; if (need == 0) { while (map[str1[l]] < 0) { map[str1[l++]]++; } min_len = MIN(min_len, r - l + 1); } } return min_len != INT_MAX ? min_len : 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str1 = br.readLine().toCharArray(); char[] str2 = br.readLine().toCharArray(); HashMap<Character, Integer> termFreq = new HashMap<>(); for(int i = 0; i < str2.length; i++) termFreq.put(str2[i], termFreq.getOrDefault(str2[i], 0) + 1); int left = 0, right = 0; int debt = str2.length; // 刚开始欠str2长度的字符 int minLen = str1.length + 1; while(right < str1.length){ if(!termFreq.containsKey(str1[right])) { right ++; // 跳过不相关的字符 continue; } termFreq.put(str1[right], termFreq.getOrDefault(str1[right], 0) - 1); if(termFreq.get(str1[right]) >= 0) debt --; if(debt == 0){ if(!termFreq.containsKey(str1[left])){ left ++; // 跳过不相关的字符 continue; } // 负债小于0的词是多余的,先去掉 while(termFreq.get(str1[left]) < 0){ termFreq.put(str1[left], termFreq.getOrDefault(str1[left], 0) + 1); left ++; } // 负债为0且无多余词,更新长度 minLen = Math.min(minLen, right - left + 1); termFreq.put(str1[left], termFreq.getOrDefault(str1[left], 0) + 1); debt ++; left ++; } right ++; } minLen = Math.min(minLen, right - left + 1); System.out.println(minLen == str1.length + 1? 0: minLen); } }
import java.util.*; public class Main{ public static int shortLengthOfStr(String A, String B) { char[] BChar = B.toCharArray(); char[] AChar = A.toCharArray(); int[] BMap = new int[256]; /** * BMap中状态:BMap中状态:0初始值,>0欠缺的值, <0不欠缺的值 */ //将欠缺哪些值压入map中 for (int i = 0; i < BChar.length; i++) { BMap[BChar[i]] ++; } int before = 0; int after = 0; int minLen = Integer.MAX_VALUE;; int match = BChar.length; while (before < AChar.length){ /** * 初始值 自减后 小于0,变成不欠缺的值 * 欠缺的值 自减后,最小变成 0 初始值 **/ BMap[AChar[before]]--; if (BMap[AChar[before]] >= 0) { //找到欠的字符,match自减,直到match=0,说明BMap中大于0的值匹配到了 match--; } if (match == 0){ //全匹配上了,开始向右移动after,after也是从0开始 //这里可以理解为找匹配字符的最左边的位置。 //例如:abcsfdr //这里找:bcd //此时,before已经到了d即index=5的位置 //要计算出长度,需要知道,最左边在{bcd}中字符的位置 //所以移动after从index=0开始,直到找到{bcd}中任意字符 //所以after移动到b即index=1,此时最短长度为 5 - 1 + 1 = 5 while (BMap[AChar[after]] < 0){ /** *小于0说明不是匹配到的数字,继续右移,直到找到最左边BChar值 因为匹配的数据是大于0,经过上面BMap[AChar[before]]--后 变成0了 **/ BMap[AChar[after]]++; after++; } minLen = Math.min(minLen, before - after + 1); //继续往下走 match++; //回补一个字符,告诉Map,哪个字符欠一个 BMap[AChar[after]]++; after++; } //向右移动before before++; } return minLen == Integer.MAX_VALUE ? 0 : minLen; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String[] data = new String[2]; int count = 0; while(scan.hasNext()){ data[count] = scan.nextLine(); count++; if (count > 1){ break; } } System.out.println(shortLengthOfStr(data[0], data[1])); } }
import java.util.Scanner;/*设str1长度为N,str2长度为M。如果N<M,那么结果必然为0。其余情况使用一个哈希表map来辅助。
- 先遍历一遍str2,生成哈希表对于字符的统计,其数值的具体意义就是str1目前还欠str2字符串key字符value个。
- 需要定义四个变量:left: str1中子串左边界;right: str1中子串右边界;match:对于所有的str2中的字符来说,str1欠str2的字符总个数;minLen: 最小子串的长度。初始时,left=0,right=0,match可由遍历str2的时候得到,minLen为32位整数最大值
- 通过right变量从左到右遍历str1,设当前位置right==i,有几种情况:
- 首先在map中把str[i]字符的value减1。如果减完之后,map[str[i]]的value大于等于0,说明str1归还了一个str[i],match也对应的-1。
- 在map中把str[i]字符的value减1,如果减完之后,map[str[i]]的value小于0,说明这个字符是目前str2不需要的,所以match不变。
- 直到某次会将match减为0时,说明str1把需要归还的字符都还完了,但此时对应的子串并不是一定最短的,因为可能有些字符归还的比较多余,此时开始向右移动left。
- 初始时left=0,把str[0]对应字符拿回来后,要在map[str[0]]位置+1,如果map[str[0]]位置没加1之前是负数,说明可以要回来。然后继续向右移动left,直到出现map[str[left]]为0时,不能再减了,否则就又亏欠了。此时出现了一个子串满足条件,更新minLen为right-left+1。至此,使得出现满足条件的子串的第一个right出现,但还是要往右扩,观察后面有没有更小的值。
- 后面的其余子串肯定比之前的子串left靠右,因为之前子串left对应的最短子串已经找到,对maxLen已经更新。所以此时令left++,同时让对应字符在map中也+1,说明又出现了亏欠str2,对应得,match也+1。然后继续right往右扩,直到match继续归0,重复这个过程,直到right到达str1的末尾。
- 如果从始至终没有更新过maxLen,说明没有匹配成功过,返回0。
时间复杂度: O(N)*/
public class Main {public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str1 = scanner.next(); String str2 = scanner.next(); int minlength = minLength(str1, str2); System.out.println(minlength); } public static int minLength(String str1, String str2) { if (str1 == null || str2 == null || str1.length() < str2.length()) { return 0; } char[] chas1 = str1.toCharArray(); char[] chas2 = str2.toCharArray(); int[] map = new int[256]; for (int i = 0; i < chas2.length; i++) { map[chas2[i]]++; } int left = 0; int right = 0; int match = chas2.length; int minLen = Integer.MAX_VALUE; while (right < chas1.length) { map[chas1[right]]--; if (map[chas1[right]] >= 0) { match--; } if (match == 0) { while (map[chas1[left]] < 0) { map[chas1[left++]]++; } minLen = Math.min(minLen, right - left + 1); match++; map[chas1[left++]]++; } right++; } return minLen == Integer.MAX_VALUE ? 0 : minLen; } }
#include <bits/stdc++.h> using namespace std; int main(){ string s1, s2; cin>>s1>>s2; int n=s1.length(), m=s2.length(), l=0, r=0, Min=INT_MAX; unordered_map<int,int> M; if(n<m){ puts("0"); return 0; } for(int i=0;i<m;i++) M[s2[i]]++; for(int i=0,k=0;i<n;i++){ M[s1[i]]--; if(M[s1[i]] >= 0){ k++; if(k==m){ while(M[s1[l]] < 0) M[s1[l++]]++; Min = min(Min, r-l+1); M[s1[l++]]++; k--; } } r++; } printf("%d\n", Min==INT_MAX?0:Min); return 0; }
public static int minLen(String a, String b){ char[] char1 = a.toCharArray(); char[] char2 = b.toCharArray(); HashMap<Character, Integer> map = new HashMap<>(); for (char c : char1) { map.put(c, 0); } for (char c : char2) { map.put(c, -1); } int match = 0; int start = 0; int end = 0; int len = Integer.MAX_VALUE; for (int i = 0; i < char1.length; i++) { if (map.get(char1[i]) == -1) { map.put(char1[i], 1); match++; if (match == char2.length) { end = i; while (map.get(char1[start]) != 1) { start++; } len = Math.min(len, end - start + 1); map.put(char1[start], -1); match--; start++; } } } return len; }
代码如下
package main import ( "fmt" "math" "strings" ) func GetMinLength(str1, str2 string)int { // 获取最短长度 left, res, match := 0, math.MaxInt32, len(str2) // 先统计str2的字符出现的频次 frequence := map[string]int{} for _, ch := range str2 { frequence[string(ch)] = strings.Count(str2, string(ch)) } for right := 0;right < len(str1);right++ { nowchar := string(str1[right]) if frequence[nowchar]--;frequence[nowchar] >= 0 { match-- if match == 0 { // 收缩左边界 for frequence[string(str1[left])] < 0 { frequence[string(str1[left])]++ left++ } res = int(math.Min(float64(res), float64(right - left + 1))) // 移动左边界 frequence[string(str1[left])]++ left++ match++ } } } if res == math.MaxInt32 { res = 0 } return res } func main() { var str1, str2 string fmt.Scan(&str1) fmt.Scan(&str2) fmt.Println(GetMinLength(str1, str2)) }
def minWindow(s, t): """ :type s: str :type t: str :rtype: str """ need,window={},{} for i in t: need[i]=need.get(i,0)+1 #定义窗口左右节点,初始化最小长度 left,right = 0,0 minlen = float('inf') #窗口包含t字符个数 count=0 while right<len(s): if need.get(s[right],0)==0: right+=1 continue window[s[right]]=window.get(s[right],0)+1 if window[s[right]]==need[s[right]]: count+=1 right+=1 #当窗口包含t所有的字符时,缩小窗口 while count==len(t): if right-left<minlen: minlen=right-left #缩小窗口 if s[left] not in need: left+=1 continue #出窗,不满足条件结束循环 if window[s[left]]==need[s[left]]: count-=1 window[s[left]]-=1 left+=1 if minlen==float('inf'): return 0 else: return minlen s=input() t=input() print(minWindow(s,t))链接:https://www.nowcoder.com/questionTerminal/58569ba19c05436e9eb492244b0902d8
#include <iostream> #include <limits> #include <string> size_t minLength(const std::string & str1, const std::string & str2) { /* 方法: * 1. 创建计数数组table,统计str2的每个字符的个数, * 2. 定义变量matched表示当前已匹配str2中字符的个数 * 3. 滑动窗口,左边界为left,右边界为right,初始都为0 * 增长右边界,每次将计数组中右边界对应的字符的计数减一, * 如果计数大于等于0,说明这个字符匹配到了str2中的字符,将matched计数加一 * 4. 判断matched是否等于str2的长度,如果等于,则说明字符已经全部匹配,此时计数数组中的元素应该全部小于等于0, * 接下来将left边界右移,移过那些不在str2中出现的字符(移动的时候要先给计数数组对应的值加1),直到匹配到一个str2的字符为止, * 如何判断匹配到str2中的字符呢?计数为0即可。 * 例如str1="AAABBB", str2="AB", 在第一次全部匹配到时, * AAABBB, 计数数组table[A]=-2, table[B]=0, 判断left当前指向的为止对应的计数是否为0,如果不是则右移 * ^ ^ * | | * left right */ std::vector<int> table(256); for(char c : str2) { table[static_cast<unsigned char>(c)]++; } const unsigned char * pStr1 = reinterpret_cast<const unsigned char *>(str1.c_str()); size_t res = std::numeric_limits<size_t>::max(); size_t left = 0; size_t right = 0; size_t matched = 0; while(right < str1.size()) { size_t c = static_cast<size_t>(str1[right]); table[c]--; if(table[c] >= 0) { matched++; } if(matched == str2.size()) // AAABBB AB { while(table[pStr1[left]] < 0) { table[pStr1[left]]++; left++; } res = std::min(res, right - left + 1); table[pStr1[left]]++; left++; matched--; } right++; } if(res == std::numeric_limits<size_t>::max()) { return 0; } return res; } int main() { std::string str1; std::string str2; std::cin >> str1; std::cin >> str2; auto res = minLength(str1, str2); std::cout << res << "\n"; return 0; }
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int hhash[256]; char str1[100010],str2[100010]; int main(){ while(~scanf("%s %s",str1,str2)){ fill(hhash,hhash+256,0); for(int i=0;i<strlen(str2);++i){ hhash[str2[i]]++; } int len1=strlen(str1),len2=strlen(str2); int maxlength=999999; int left=0,right=0,match=len2; for(int i=0;i<len1;++i){ hhash[str1[i]]--; if(hhash[str1[i]]>=0){ match--; if(match==0){ while(hhash[str1[left]]<0) { hhash[str1[left]]++; left++; } if((right-left+1)<maxlength) maxlength=right-left+1; hhash[str1[left]]++; left++; match++; } } right++; } printf("%d",maxlength==999999?0:maxlength); } return 0; }