-
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
法一：Rabin-Karp
class Solution {
public:
int strStr(string haystack, string needle) {
int b = 131, p = 1e9 + 7;
int n = haystack.length(), m = needle.length();
vector<long long> H(n + 1);
H[0] = 0;
for (int i = 1; i <= n; i++)
H[i] = (H[i - 1] * b + (haystack[i - 1] - 'a' + 1)) % p;
long long Hneedle = 0, powBM = 1;
for (int i = 1; i <= m; i++) {
Hneedle = (Hneedle * b + (needle[i - 1] - 'a' + 1)) % p;
powBM = powBM * b % p;
}
for (int l = 1; l <= n - m + 1; l++) {
int r = l + m - 1;
if (((H[r] - H[l - 1] * powBM) % p + p) % p == Hneedle)
return l - 1;
}
return -1;
}
};
法二：KMP
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.length(), m = needle.length();
haystack = ' ' + haystack, needle = ' ' + needle;
vector<int> next(m + 1);
next[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && needle[i] != needle[j + 1])
j = next[j];
if (needle[i] == needle[j + 1])
j++;
next[i] = j;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && haystack[i] != needle[j + 1])
j = next[j];
if (j < m && haystack[i] == needle[j + 1])
j++;
if (j == m) return i - m;
}
return -1;
}
};
class Solution {
public:
bool isPalindrome(string s) {
int l = getNext(s, 0), r = getPre(s, s.length() - 1);
while (l < r) {
if (!equals(s[l], s[r]))
return false;
l = getNext(s, l + 1);
r = getPre(s, r - 1);
}
return true;
}
private:
bool isDigitOrLetter(char ch) {
return ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9';
}
int getNext(string& s, int i) {
while (i < s.length() && !isDigitOrLetter(s[i]))
i++;
return i;
}
int getPre(string& s, int i) {
while (i >= 0 && !isDigitOrLetter(s[i]))
i--;
return i;
}
bool equals(char ch1, char ch2) {
if (ch1 >= 'A' && ch1 <= 'Z')
ch1 = ch1 - 'A' + 'a';
if (ch2 >= 'A' && ch2 <= 'Z')
ch2 = ch2 - 'A' + 'a';
return ch1 == ch2;
}
};
class Solution {
public:
bool validPalindrome(string s) {
return check(s, 0, s.length() - 1, 1);
}
private:
bool check(string& s, int l, int r, int times) {
while (l < r) {
if (s[l] != s[r])
return times > 0
&& (check(s, l, r - 1, times - 1) || check(s, l + 1, r, times - 1));
l++, r--;
}
return true;
}
};
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
int start = 0, len = 0;
// odd
for (int i = 0; i < n; i++) {
int l = i - 1, r = i + 1;
while (l >= 0 && r < n && s[l] == s[r])
l--, r++;
// [l+1, r-1]
if (r - l - 1 > len) {
len = r - l - 1;
start = l + 1;
}
}
// even
for (int i = 1; i < n; i++) {
int l = i - 1, r = i;
while (l >= 0 && r < n && s[l] == s[r])
l--, r++;
// [l+1, r-1]
if (r - l - 1 > len) {
len = r - l - 1;
start = l + 1;
}
}
return s.substr(start, len);
}
};
class Solution {
public:
bool isMatch(string s, string p) {
// T0. Move index to 1-based
int n = s.length(), m = p.length();
s = ' ' + s, p = ' ' + p;
// T1. Define f, initialize
//// f[i][j] 表示s的前i个字符，p的前j个字符，能否匹配
vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
f[0][0] = true;
for (int i = 2; i <= m; i += 2)
if (p[i] == '*') f[0][i] = true;
else break;
// T2. Loop over all states
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
// T3. Copy decision funcs
if (p[j] >= 'a' && p[j] <= 'z')
f[i][j] = f[i - 1][j - 1] && s[i] == p[j];
else if (p[j] == '.')
f[i][j] = f[i - 1][j - 1];
else {
f[i][j] = f[i][j - 2];
if (s[i] == p[j - 1] || p[j - 1] == '.')
f[i][j] = f[i][j] || f[i - 1][j];
}
return f[n][m];
}
};
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.length(), m = t.length();
// 0. Move index to 1-base
s = " " + s, t = " " + t;
// 1. Define f, initialize
vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i <= n; i++) f[i][0] = 1;
// 2. Loop over all states
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
// 3. Copy decision funcs
// 3.1 不要s[i]
f[i][j] = f[i - 1][j];
// 3.2 要s[i]
if (s[i] == t[j] && f[i][j] <= 2147483647 - f[i - 1][j - 1])
f[i][j] += f[i - 1][j - 1];
}
// 4. Return target
return f[n][m];
}
};
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
unordered_set<char> row[9];
unordered_set<char> col[9];
unordered_set<char> box[9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
char digit = board[i][j];
if (digit == '.') continue;
if (row[i].find(digit) != row[i].end()) return false;
row[i].insert(digit);
if (col[j].find(digit) != col[j].end()) return false;
col[j].insert(digit);
int k = i / 3 * 3 + j / 3;
if (box[k].find(digit) != box[k].end()) return false;
box[k].insert(digit);
}
return true;
}
};
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++)
for (int digit = 1; digit <= 9; digit++)
row[i][digit] = col[i][digit] = box[i][digit] = true;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') continue;
int digit = board[i][j] - '0';
row[i][digit] = false;
col[j][digit] = false;
box[boxIdx(i, j)][digit] = false;
}
dfs(board);
}
private:
bool dfs(vector<vector<char>>& board) {
pair<int, int> pos = findMinPro(board);
int x = pos.first, y = pos.second;
if (x == -1) return true;
vector<int> leftDigits = getLeftDigits(x, y);
for (int digit : leftDigits) {
board[x][y] = '0' + digit;
row[x][digit] = false;
col[y][digit] = false;
box[boxIdx(x, y)][digit] = false;
if (dfs(board)) return true;
box[boxIdx(x, y)][digit] = true;
col[y][digit] = true;
row[x][digit] = true;
board[x][y] = '.';
}
return false;
}
pair<int, int> findMinPro(vector<vector<char>>& board) {
int minVal = 10;
pair<int, int> pos = {-1, -1};
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue;
vector<int> leftDigits = getLeftDigits(i, j);
if (leftDigits.size() < minVal) {
minVal = leftDigits.size();
pos = {i, j};
}
}
return pos;
}
vector<int> getLeftDigits(int i, int j) {
vector<int> res;
for (int digit = 1; digit <= 9; digit++)
if (row[i][digit] && col[j][digit] && box[boxIdx(i, j)][digit])
res.push_back(digit);
return res;
}
int boxIdx(int i, int j) {
return i / 3 * 3 + j / 3;
}
bool row[9][10];
bool col[9][10];
bool box[9][10];
};
