力扣2781.最长合法子字符串的长度
力扣2781.最长合法子字符串的长度
将字符串数组存入哈希表
- 枚举所有右端点
- 反向遍历子串在哈希表中找所有以i为右端点的字符串
- 若找到相同子串 更新j = k + 1
class Solution { public: int longestValidSubstring(string word, vector<string>& forbidden) { unordered_set<string> fb(forbidden.begin(),forbidden.end()); int res=0,n = word.size(); for(int i=0,j=0;i<n;i++) { //遍历子串左端点 for(int k=i;k>=j&k>i-10;k--) //(k,i)的子串 在哈希表中找一下 if(fb.count(word.substr(k,i-k+1))) j = k+1; res = max(res,i-j+1); } return res; } };