1.LeetCode:2315. 统计星号
原题链接
给你一个字符串 s ，每 两个 连续竖线 ‘|’ 为 一对 。换言之，第一个和第二个 ‘|’ 为一对，第三个和第四个 ‘|’ 为一对，以此类推。
请你返回 不在 竖线对之间，s 中 ‘’ 的数目。
注意，每个竖线 ‘|’ 都会 恰好 属于一个对。
示例 1：
输入：s = "l|eet|co|de|"
输出：2
示例 2：
输入：s = “iamprogrammer”
输出：0
示例 3：
输入：s = "yo|uar|e|b|eau|tifu|l"
输出：5
提示：
1 <= .length <= 1000
s 只包含小写英文字母，竖线 ‘|’ 和星号 '’ 。
s 包含 偶数 个竖线 ‘|’ 。
很简单的一道题目，找到判断当前 | 出现次数，如果是偶数就说明之前的 | 均已匹配，可以对*计数。
class Solution {
public:
int countAsterisks(string s) {
int cnt=0;
int ans=0;
for(auto i:s){
if(i=='|'){
cnt++;
}else {
if(!(cnt&1)){
ans+=i=='*'?1:0;
}
}
}
return ans;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
2.LeetCode:459. 重复的子字符串
原题链接
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab”
输出: true
示例 2
输入: s = “aba”
输出: false
示例 3:
输入: s = “abcabcabcabc”
输出: true
提示：
1 <= s.length <= 104
s 由小写英文字母组成
这种也是典型题目了：找最小循环节，那么方法也自然有很多比如KMP。
KMP的做法就很简单了，求出next数组(这里存长度就好了，不用存下标了），然后看len%(len-next[len-1])==0(有循环节就说明去掉前缀或者是一样的）并且next[len-1]!=0就返回true，否则false。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int next[10010];
next[0]=0;
int j=0;
for(int i=1;i<s.size();++i){
while(j>0&&s[j]!=s[i]) j=next[j-1];
if(s[i]==s[j]) ++j;
next[i]=j;
}
int len=s.size();
if(next[len-1]!=0&&(len%(len-next[len-1]))==0){
return true;
}
return false;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
当然也有取巧的做法，既然是存在循环节，那么就从第一个位置在s+s寻找s是否存在。不过这只能判断s存在循环节并不知道它是不是最小的，不过这样很适合本题就是了
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string tmp=s+s;
return tmp.find(s,1)!=s.size();
}
};
3.LeetCode:1790. 仅执行一次字符串交换能否使两个字符串相等
原题链接
给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
示例 1：
输入：s1 = “bank”, s2 = “kanb”
输出：true
示例 2：
输入：s1 = “attack”, s2 = “defend”
输出：false
示例 3：
输入：s1 = “kelb”, s2 = “kelb”
输出：true
示例 4：
输入：s1 = “abcd”, s2 = “dcba”
输出：false
提示：
1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 和 s2 仅由小写英文字母组成
典型的水题，因为s1和s2长度相同，我们直接遍历统计其中不同的字符，如果dif为0直接返回true，如果dif==2，则交换这两个不同的位置返回s1 == s2,其他均返回false。
class Solution {
public:
bool areAlmostEqual(string s1, string s2) {
int dif=0;
vector<char> ans;
for(int i=0;i<s1.size();++i){
if(s1[i]!=s2[i]){
dif++;
ans.push_back(i);
}
}
if(dif==0){
return true;
}else if(dif==2){
swap(s2[ans[0]],s2[ans[1]]);
return s1==s2;
}
return false;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
4.LeetCode:1961. 检查字符串是否为数组前缀
原题链接
给你一个字符串 s 和一个字符串数组 words ，请你判断 s 是否为 words 的 前缀字符串 。
字符串 s 要成为 words 的 前缀字符串 ，需要满足：s 可以由 words 中的前 k（k 为 正数 ）个字符串按顺序相连得到，且 k 不超过 words.length 。
如果 s 是 words 的 前缀字符串 ，返回 true ；否则，返回 false 。
示例 1：
输入：s = “iloveleetcode”, words = [“i”,“love”,“leetcode”,“apples”]
输出：true
示例 2：
输入：s = “iloveleetcode”, words = [“apples”,“i”,“love”,“leetcode”]
输出：false
提示：
1 <= words.length <= 100
1 <= words[i].length <= 20
1 <= s.length <= 1000
words[i] 和 s 仅由小写英文字母组成
也是个水题，直接模拟words的前k个元素相加是否与s相等即可。
class Solution {
public:
bool isPrefixString(string s, vector<string>& words) {
for(int k=1;k<=words.size();++k){
string tmp="";
for(int i=0;i<k;++i){
tmp+=words[i];
}
if(s==tmp){
return true;
}
}
return false;
}
};
