28. 实现 strStr()
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1
示例 3：
输入：haystack = “”, needle = “”
输出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
1. 暴力匹配
class Solution {
public:
int strStr(string haystack, string needle) {
if(!needle.size())return 0;
for(int i=0;i<haystack.size();i++){
if(haystack[i]==needle[0]){
bool flag=1;
for(int j=0;j<needle.size();j++){
if(haystack[i+j]!=needle[j]){
flag=0;
break;
}
}
if(flag)return i;
}
}
return -1;
}
};
2. hash
using ULL = unsigned long long;
const int base = 13331;
const int maxn = 5e4 + 50;
ULL h1[maxn],h2[maxn],f[maxn];
ULL get(int l,int r){
if(l == 0) return h1[r];
return h1[r] - h1[l - 1] * f[r - l + 1];
}
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.size() == 0) return 0;
int n = haystack.size(), m = needle.size();
f[0] = 1;
for(int i = 1; i < max(m,n); i++){
f[i] = f[i - 1] * base;
}
for(int i = 0; i < n; i++){
if(i == 0) h1[i] = haystack[i];
else h1[i] = h1[i - 1] * base + haystack[i];
}
for(int i = 0; i < m; i++){
if(i == 0) h2[i] = needle[i];
else h2[i] = h2[i - 1] * base + needle[i];
}
for(int i = 0; i + m - 1 < n; i++){
if(get(i,i + m - 1) == h2[m - 1]){
return i;
}
}
return -1;
}
};
3. KMP
class Solution {
public:
int strStr(string haystack, string needle) {
if(!needle.size())return 0;
int n=haystack.size(),m=needle.size();
vector<int> next(m+1,0);
for(int i=1,j=0;i<m;i++){
while(j>0&&needle[i]!=needle[j])j=next[j-1];
if(needle[i]==needle[j])j++;
next[i]=j;
}
for(int i=0,j=0;i<n;i++){
while(j>0&&haystack[i]!=needle[j])j=next[j-1];
if(haystack[i]==needle[j])j++;
if(j==m)return i-m+1;
}
return -1;
}
};
524. 通过删除字母匹配到字典里最长单词
给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：
输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”
示例 2：
输入：s = “abpcplea”, dictionary = [“a”,“b”,“c”]
输出：“a”
提示：
1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
string ans="";
for(auto word:dictionary){
if(word.size()<ans.size())continue;
if(word.size()==ans.size()&&word>=ans)continue;
if(word.size()>s.size())continue;
int j=0;
for(int i=0;i<s.size();i++){
if(s[i]==word[j]){j++;}
if(j==word.size()){
ans=word;
break;
}
}
}
return ans;
}
};
- 直接判断是不是子串
1392. 最长快乐前缀(longestPrefix)
「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀，则返回一个空字符串。
示例 1：
输入：s = “level”
输出：“l”
解释：不包括 s 自己，一共有 4 个前缀（“l”, “le”, “lev”, “leve”）和 4 个后缀（“l”, “el”, “vel”, “evel”）。最长的既是前缀也是后缀的字符串是 “l” 。
示例 2：
输入：s = “ababab”
输出：“abab”
解释：“abab” 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
示例 3：
输入：s = “leetcodeleet”
输出：“leet”
示例 4：
输入：s = “a”
输出：""
提示：
1 <= s.length <= 10^5
s 只含有小写英文字母
1. KMP
class Solution {
public:
string longestPrefix(string s) {
vector<int>next(s.size(),0);
for(int i=1,j=0;i<s.size();i++){
while(j>0&&s[i]!=s[j])j=next[j-1];
if(s[i]==s[j])j++;
next[i]=j;
}
return s.substr(0,next[s.size()-1]);
}
};
题解：https://leetcode-cn.com/problems/longest-happy-prefix/solution/zui-chang-kuai-le-qian-zhui-by-leetcode-solution/
HASH:Rabin-Karp 字符串编码
class Solution {
public:
string longestPrefix(string s) {
int base=31,mod=1e9+7;
int mul=1,ans=0;
int perfix=0,surfix=0;
for(int i=0;i<s.size()-1;i++){
perfix=((long long)perfix*base+s[i]-'a')%mod;
surfix=(surfix+(long long)(s[s.size()-1-i]-'a')*mul)%mod;
if(surfix==perfix){
ans=i+1;
}
mul=(long long)mul*base%mod;
}
return s.substr(0,ans);
}
};
- 注意溢出的处理
|