[LeetCode] Minimum Window Substring

简介: This post shares a nice explanation, which is implemented here. The code is rewritten below. 1 class Solution { 2 public: 3 string minWindow(string s, string t) { 4 int m = s.

This post shares a nice explanation, which is implemented here. The code is rewritten below.

 1 class Solution {
 2 public:
 3     string minWindow(string s, string t) {
 4         int m = s.length(), n = t.length();
 5         if (!m || !n) return "";
 6         int times[128] = {0};
 7         bool exist[128] = {false};
 8         for (int i = 0; i < n; i++) {
 9             times[t[i]]++;
10             exist[t[i]] = true;
11         }
12         int l = 0, r = -1, idx = 0, len = INT_MAX;
13         while (l < m && r < m) {
14             if (n) {
15                 times[s[++r]]--;
16                 if (exist[s[r]] && times[s[r]] >= 0) n--;
17             }
18             else {
19                 if (len > r - l + 1) {
20                     len = r - l + 1;
21                     idx = l;
22                 }
23                 times[s[l]]++;
24                 if (exist[s[l]] && times[s[l]] > 0) n++;
25                 l++;
26             }
27         }
28         return len == INT_MAX ? "" : s.substr(idx, len);
29     }
30 };

 

目录
相关文章
|
Java
Leetcode 3. Longest Substring Without Repeating Characters
此题题意是找出一个不包含相同字母的最长子串,题目给出了两个例子来说明题意,但这两个例子具有误导性,让你误以为字符串中只有小写字母。还好我是心机boy,我把大写字母的情况也给考虑进去了,不过。。。。字符串里竟然有特殊字符,于是贡献了一次wrong answer,这次我把ascii字符表都考虑进去,然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围,面试中可以和面试官去确认数据范围,也能显得你比较严谨。
54 3
|
索引
LeetCode 76. Minimum Window Substring
给定一个字符串S和一个字符串T,找到S中的最小窗口,它将包含复杂度为O(n)的T中的所有字符。
68 0
LeetCode 76. Minimum Window Substring
|
Java 程序员 开发者
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二:编码实现
本文是《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲》的第二篇,前一篇文章已经列出了完整的解题思路,今天来将此思路转化为具体的Java代码
105 0
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二:编码实现
|
Java 程序员 开发者
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之一:解题思路
本文回顾了笔者对LeetCode第三题(Longest Substring Without Repeating Characters)的解题和优化思路,希望有兴趣的读者来一起广泛讨论
110 1
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之一:解题思路
|
Java 程序员 开发者
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三:两次优化
本文是《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲》的第二篇,前一篇文章已经列出了完整的解题思路,今天来将此思路转化为具体的Java代码
106 0
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三:两次优化
|
索引
Leetcode-Medium 5. Longest Palindromic Substring
Leetcode-Medium 5. Longest Palindromic Substring
122 0
|
存储 Java 索引
LeetCode 3: 无重复字符的最长子串 Longest Substring Without Repeating Characters
题目: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 Given a string, find the length of the longest substring without repeating characters. 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
1006 0