从Leetcode 每日一题练习继续讨论：
1813. 句子相似性 III
1813. Sentence Similarity III
题解
本题只能插入一个句子，则要在插入一个句子后将短句变为长句，短句拆分后的前后两部分应分别位于长句的首尾部分（可以拆为空句，这样就是短句完全是长句的开头部分或者结尾部分），则遍历两个句子，匹配开头部分，不匹配时继续向后遍历长句直到可以继续匹配，此时匹配的是短句的后半部分，注意可能存在短句的后半部分的的某部分被重复匹配的情况，即假设短句为aaab，长句可能为aaaaab，因此需要一个指针记录匹配短句后半部分时的起始位置，另外一个指针则进行正常的长短句匹配。
代码
class Solution {
public:
bool areSentencesSimilar(string sentence1, string sentence2) {
vector<string> s1;
vector<string> s2;
istringstream iss1(sentence1);
istringstream iss2(sentence2);
string word;
while(iss1 >> word){
s1.push_back(word);
}
while(iss2 >> word){
s2.push_back(word);
}
if (s1.size() > s2.size()){
swap(s1,s2);
}
int start = 0;
for (;start<s1.size();start++){
if(s1[start] != s2[start]){
break;
}
}
int tail = start;
if (tail == s1.size()){
return true;
}
int s2ptr = start;
// cout << tail << " "<<s2ptr<<" "<<s1.size() << s2.size();
for(;s2ptr<s2.size();s2ptr++){
if (tail >= s1.size()){
tail = start;
}
if(s2[s2ptr] != s1[tail]){
tail = start;
if(s2[s2ptr] == s1[tail]){
tail++;
}
}else{
tail++;
}
}
if (tail == s1.size()){
return true;
}
return false;
}
};
总结
使用KMP算法应该还可以对字符串匹配的过程做进一步的优化，把每个单词视为kmp中的字母，即可使用同样的方案加速匹配，在这里就不继续改进了。
本题还可采用将短句视为一个双端队列，遍历短句时同时将短句头部和长句头部，短句尾部和长句尾部进行匹配，任意一端匹配成功则弹出一个单词，两端都不匹配的时候结束遍历，判断短句是否已经全部弹出即可得到结果，空则说明可以匹配上，非空则不能匹配上。
class Solution {
public:
bool areSentencesSimilar(string sentence1, string sentence2) {
deque<string> v1, v2;
stringstream ss(sentence1);
string s;
while(getline(ss,s,' ')){
v1.push_back(s);
}
stringstream ss2(sentence2);
while(getline(ss2,s,' ')){
v2.push_back(s);
}
if(v1.size() > v2.size()) swap(v1,v2);
while(v1.size()){
if(v1.front() == v2.front()){
v1.pop_front();
v2.pop_front();
} else if(v1.back() == v2.back()){
v1.pop_back();
v2.pop_back();
} else {
break;
}
}
return v1.empty();
}
};