【每日编程-450期】Leetcode.1002.查找常用字符
样例一：
输入：["bella","label","roller"]
输出：["e","l","l"]
样例二：
输入：["cool","lock","cook"]
输出：["c","o"]
提示：
1 <= A.length <= 1001 <= A[i].length <= 100A[i][j]是小写字母
解决方法：
（1）算法的基本思想：
本题可以理解为求每个字符串之间字符数量的交集，以示例1为例：
输入：["bella","label","roller"]
输出：["e","l","l"]
我们知道第一个字符串的字符数量列表为：
b 1
e 1
l 2
a 1
第二个字符串的字符数量列表为：
l 2
a 1
b 1
e 1
第三个字符串的字符数量列表为：
r 2
o 1
l 2
e 1
这三个求交集后的结果为：
e 1
l 2
结果一目了然。
分析到这里其实也没啥好说的了，我们可以用hashmap来表示**字符-数量**之间的关系，但是考虑到效率的问题，我们可以使用数组来对代码进行优化。用数组res的下标i表示是哪个字符，用res[i]表示该字符出现的次数。
作者@梁越勇：https://leetcode-cn.com/u/enoch_liang/
（2）代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
vector<string> commonChars(vector<string> &A)
{
//用数组实现hash,下标表示字母,值表示字母出现次数，初始化为最大值
vector<int> count(26, INT_MAX);
for (int i = 0; i < A.size(); ++i)
{
int word[26] = {0};
for (int j = 0; j < A[i].size(); ++j)
{
//使用ASCII码
word[(int)(A[i][j] - 'a')]++;
}
for (int j = 0; j < 26; ++j)
{
//对每个字符串求交,出现次数少的获胜
count[j] = min(count[j], word[j]);
}
}
vector<string> res;
for (int i = 0; i < count.size(); ++i)
{
if (count[i] > 0)
{
string str;
str.push_back((char)('a' + i));
for (int j = 0; j < count[i]; ++j)
{
res.push_back(str);
}
}
}
return res;
}
};
int main()
{
Solution A;
vector<string> s = {"bella", "label", "roller"};
vector<string> res;
res = A.commonChars(s);
for (auto c : res)
{
cout << c;
}
return 0;
}
样例：
输入: "aba", "cdc"
输出: 3
解析: 最长特殊序列可为 "aba" (或 "cdc")
说明:
两个字符串长度均小于100。
字符串中的字符仅含有 'a'~'z'。
class Solution {
public:
int findLUSlength(string a, string b) {
}
};