686. 重复叠加字符串匹配
给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。
举个例子，A = "abcd"，B = "cdabcdab"。
答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。
注意:
A 与 B 字符串的长度在1和10000区间范围内。
第一版，很精妙,很经典，很厉害
执行用时 :16 ms, 在所有 cpp 提交中击败了92.28%的用户
内存消耗 :9.2 MB, 在所有 cpp 提交中击败了78.79%的用户
if (A.empty()) {
return-1;
}
stringT=A;
inti=1;
while (T.size() <B.size()) {
T.append(A);
++i;
}
//A的长度大于等于B了
if (T.find(B) !=string::npos) {//顺序增长的就可以了,比如abcd 和 abcdabcdabcd
returni;
}
T.append(A);
++i;
if (T.find(B) !=string::npos) { //不是按序增长，比如abcd 和 cdabcdabcdabcdab
returni;
}
return-1;
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
- 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
第一版，想差了，不应该用间两端扩展法的
abc
aba
aeeeee
boolequal(string&s, intlow, inthigh) {
intcut=0;
if (low==high) {
low--;
high++;
cut++;
}
while (low>=0&&high<s.size()) {
if (s[low] ==s[high]) {
low--;
high++;
}
else
{
cut++;
low--;
high++;
}
if (cut==2) returnfalse;
}
returnlow==-1&&high==s.size();
}
boolvalidPalindrome(strings) {
if (s.size() <3) returntrue;
intlen=s.size();
if (len%2==0) returnequal(s, -1+len/2, len/2);
else
returnequal(s, len/2, len/2);
}
第二版，应该从两端向中间进发
从两端向中间进发，遇到不相等的了就加一或者减一再进行判断
，千万注意边界的判断情况
执行用时 :80 ms, 在所有 cpp 提交中击败了74.60%的用户
内存消耗 :21.7 MB, 在所有 cpp 提交中击败了89.60%的用户
boolequal(string&s, intlow, inthigh) {
while (low<high&&s[low] ==s[high]) {
low++;
high--;
}
returnlow>=high;
}
boolvalidPalindrome(strings) {
if (s.size() <3) returntrue;
intlow=0,high=s.size()-1;
while (s[low] ==s[high]&&low<high) {
low++;
high--;
}
if (low==high|| low-high==1) returntrue;
elseif (equal(s, low+1, high) ||equal(s, low, high-1))
returntrue;
else
returnfalse;
}
434. 字符串中的单词数
统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:
输入: "Hello, my name is John"
输出: 5
第一版，这里对单词的定义很不一样。。。
执行用时 :4 ms, 在所有 cpp 提交中击败了65.68%的用户
内存消耗 :8.5 MB, 在所有 cpp 提交中击败了23.30%的用户
intcountSegments(strings) {
intcut=0;
stringword;
for (auto&a : s) {
if (a==' '&&word!="") {
cut++;
//cout << word << endl;
word="";
}
elseif (a==' '&&word=="") continue;
else
{
word+=a;
}
}
if (word!="") cut++;
returncut;
}
第二版，利用stringstream来实现
执行用时 :4 ms, 在所有 cpp 提交中击败了65.68%的用户
内存消耗 :8.5 MB, 在所有 cpp 提交中击败了33.50%的用户
是以空格作为分隔符的，很巧妙的流的概念：stringsstream
intcountSegments(strings) {
stringstr;
intcount=0;
stringstreamss;
ss<<s;
while (ss>>str)
count++;
returncount;
}
