LeetCode:1408.数组中的字符串匹配

C++代码一：

class Solution {
public:vector<string> stringMatching(vector<string>& words) {unordered_set<string> result;int n = words.size();for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {// 跳过自身，且子串长度必须小于主串if (i == j || words[i].size() >= words[j].size()) {continue;}// 用find判断words[i]是否是words[j]的子串if (words[j].find(words[i]) != string::npos) {result.insert(words[i]);}}}return vector<string>(result.begin(), result.end());}
};

这个方法遍历所有字符串对，通过find函数判断其中较短的字符串是否是较长字符串的子串，收集所有满足条件的较短字符串，去重后返回。

C++代码二：

class Solution {
public:vector<string> stringMatching(vector<string>& words) {string tem="";for(string s:words){tem+=s;tem+=' ';               // 防止两个字符首位连接的部分刚好形成一个子串，用空格区分}vector<string> ans;for(string x:words){if(tem.find(x)!=tem.rfind(x)){   //从前后两个方向查找，如果pos不同则代表出现两次以上，必是子串。ans.push_back(x);}}return ans;}
};

这个代码的做法非常巧妙，核心是通过拼接所有字符串并利用前后查找位置的差异来判断一个字符串是否是其他字符串的子串。

将所有字符串拼接成一个大字符串，通过判断某个字符串在拼接后的字符串中是否出现至少两次，来确定它是否是其他字符串的子串。因为自身会出现一次，若额外出现一次则必是其他字符串的子串。