Skip to main content

字符串专题

无重复最长子串

tip

哈希表+双指针

思路:使用一个哈希表存储字符的数量,然后用两个指针算法进行遍历判断

核心代码

string s = "abcabcbb";
int ans;
unordered_map<int,int> hash;
int l = 0, r = 0;
hash[s[0]]++;
while(l <= r and r < s.size())
{
hash[s[++r]]++;
while(hash[s[r]] > 1) hash[s[l++]]--;
ans = max(ans, r - l + 1);
}

最长回文串

tip

中心扩展算法,回文串可能是偶数的也可能是奇数的。偶数和奇数需要单独进行判断

核心代码

string s = "babad";
int res = 0;
string ans;
for(int i = 0;i < s.size();i++)
{
// 寻找以i作为中心的回文串
for(int j = 0;i - j >= 0 and i + j < s.size();j++)
{
if(s[i-j] == s[i+j])
{
if(j * 2 - 1 > res)
{
res = 2 * j + 1;
ans = s.substr(i-j,res);
}
}
else break;
}
// 寻找以i为中心的偶数长度的回文串
for(int j = i,k = i + 1;j >= 0 and k < s.size();j--,k++)
{
if(s[j] == s[k])
{
if(k - j + 1 > res)
{
res = k -j + 1;
ans = s.substr(j,res);
}
}else break;
}
}

有效括号

tip

栈 + 双指针

核心代码

string s = "(()"
stack<int> stk; // 栈存储下标
int res = 0;
// start 用来记录当前有效括号开始的坐标
// 否则栈空的时候就无法计算当前有效括号的长度了
for(int i = 0,start = -1;i < s.size();i++)
{
if(s[i] == '(') stk.push_back(i)
else
{
if(s[i].size())
{
stk.pop();
if(stk.size())
res = max(res,i - stk.top());
else
res = max(res,i - start);
}
else start = i; // 开始新一轮的匹配
}
}

最小覆盖子串

tip

给定一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。

思路:哈希表+双指针

核心代码

string s = "ADOBECODEBANC";
string t = "ABC";
string res;
unordered_map<string,int> hs, ht;
for(auto item:t) ht[item]++;
int cnt = 0;
for(int i = 0,j = 0;i < s.size();i++)
{
hs[s[i]]++;
if(hs[s[i]] <= ht[s[i]]) cnt++; // 避免重复计数
while(hs[s[j]] > ht[s[i]]) hs[s[j++]]--;
if(cnt == t.size())
{
if(res.empty() and i - j + 1 < res.size())
res = s.substr(i,i-j+1);
}
return res;
}