1.判断子序列
题目
解析
代码
class Solution {
public:bool isSubsequence(string s, string t) {// 时间复杂度：O(m)// 空间复杂度：O(1)int n = s.size(),m = t.size();int i = 0,j = 0;while(i < n && j < m){if(s[i] == t[j]) {i ++,j ++;}else {j ++;}}return i == n;}
};
2.通过删除字母匹配到字典里最长单词
题目
解析
- 判断子序列思路一致；
- 长度不相等：取最长；长度相等：取字典序最小；
- 注意点：长度不相等更新答案，同时也要更新最长长度；
代码
class Solution {bool check(string s,string t){int n = s.size(),m = t.size();int i = 0,j = 0;while(i < n && j < m){if(s[i] == t[j]){i ++,j ++;}else {j ++;}}return i == n;}public:string findLongestWord(string s, vector<string>& dictionary) {string ans = "";int n = ans.size();for(string word : dictionary){if(check(word,s)){int x = word.size();if(x > n) {ans = word;n = x;// 更新长度}else if(x == n) {ans = min(ans,word);}}}return ans;}
};
3.追加字符以获得子序列
题目
解析
代码
class Solution {
public:int appendCharacters(string s, string t) {// 时间复杂度：O(n + m)// 空间复杂度：O(1)int n = s.size(),m = t.size();int i = 0,j = 0;while(i < n && j < m){if(s[i] == t[j]) {i ++,j ++;}else{i ++;}}return m - j;}
};
4.循环增长使字符串子序列等于另一个字符串
题目
解析
代码
class Solution {char tran(char a){char ans;if(a >= 'a' && a <= 'y') ans = ++ a;else if(a == 'z') ans = 'a';return ans;}
public:bool canMakeSubsequence(string str1, string str2) {// 时间复杂度：O(n + m)// 空间复杂度：O(1)int n = str1.size(),m = str2.size();int i = 0,j = 0;while(i < n && j < m){if(str1[i] == str2[j] || tran(str1[i]) == str2[j]){i ++,j ++;}else{i ++;}}return j == m;}
};
5.驼峰式匹配
题目
解析
- 题目要求：在为子序列的同时，不能出现匹配字母外的大写字母；
- 所以有两个地方要进行判断：
- 一个是匹配子序列的过程中出现了非原序列的大写字母；
- 第二个是匹配完之后，原序列后面可能还存在大写字母；
代码
class Solution {auto check(string s,string t){int n = s.size(),m = t.size();int i = 0,j = 0;while(i < n && j < m){if(s[i] == t[j]){i ++,j ++;}else if(isupper(t[j])){return false;}else{j ++;}} while(j < m){if(isupper(t[j])) return false;j ++;}return i == n;}public:vector<bool> camelMatch(vector<string>& queries, string pattern) {// 时间复杂度：O(m*n)// 空间复杂度：O(1)vector<bool> ans;for(string word : queries){ans.push_back(check(pattern,word));}return ans;}
};
