思路：
题目的主要信息：
- n个字符串，从第一个字符串开始作为左边个单词，依次遍历后面的作为右边单词
- 当左边单词的尾字符与右边单词的首字符相同是，消去这两个字符，消去之后继续比较，如此循环直到不同
- 将左边单词与右边单词首尾拼接作为下轮的左边单词，往后遍历
- 求遍历完最后剩余的字符串
方法一：直接比较+字符串截取
具体做法：
我们直接用a和b表示左右两个字符串，初始a为第0个字符串，b为第1个字符串，然后用下标比较二者的首尾，找到第一个不同的a字符串尾和b字符串首，然后用字符串截取函数substr截取a从头到不相同的第一位，b的不相同第一位到尾，将二者拼接作为新的字符串a，进入后续遍历。
class Solution {
public:
string WordsMerge(vector<string>& Words) {
string a = Words[0]; //记录左边的字符串
for(int i = 1; i < Words.size(); i++){
string b = Words[i]; //记录右边一个字符串
int j;
for(j = 0; j < min(a.length(), b.length()); j++){ //遍历两字符串较短的一个长度
if(a[a.length() - j - 1] != b[j]) //如果首尾字符不相等则跳出
break;
}
a = a.substr(0, a.length() - j) + b.substr(j); //去掉相同部分
}
return a;
}
};复杂度分析：
- 时间复杂度：
，最坏情况全部字符都可以消除
- 空间复杂度：
，字符串a属于返回必要空间，不属于额外空间
方法二：栈
具体做法：
借助栈来记录左边单词的字符，每次遇到一个字符串我们就比较前缀与栈顶，如果相同则弹出栈顶元素，继续往后比较，如果找到了第一个不相同的元素，则后续元素全部入栈。最后将栈中字符弹出逆序相加就是答案。
class Solution {
public:
string WordsMerge(vector<string>& Words) {
stack<char> s;
for(int i = 0; i < Words[0].size(); i++)
s.push(Words[0][i]); //首单词入栈
for(int i = 1; i < Words.size(); i++){
bool flag = false; //找到第一个不相同的点置为true，flag为true后续都要入栈
for(int j = 0; j < Words[i].length(); j++){ //遍历该字符串
if((j == 0 && s.empty()) || flag){ //首尾遇到空栈或者已经找到了第一个不相同的点，剩下全部入栈
flag = true;
s.push(Words[i][j]);
}
else{
if(s.top() == Words[i][j]) //相同弹出
s.pop();
else{
s.push(Words[i][j]); //第一个不相同的点
flag = true;
}
}
}
}
string res = "";
while(!s.empty()){
res = s.top() + res; //逆序相加
s.pop();
}
return res;
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号