最長回文子串
1. 題目
已知一個只包含大小寫的字符串合溺，求用該字符串可以生成的最長回文子串的長度。
2. 思路
首先要考慮回文字符串的性質(zhì)：當(dāng)字符個數(shù)為奇數(shù)時庇谆，左右關(guān)與某個字符對稱岳掐，當(dāng)字符個數(shù)為偶數(shù)時左右對稱。為此可以想到如果在字符串中有奇數(shù)個某字符可以去掉一個該字符使用剩下的偶數(shù)個來構(gòu)成回文字符串饭耳，如果某個字符在字符串中有偶數(shù)個可以直接用來構(gòu)成回文串串述。最后如果字符有剩余，可直接從中取一個字符作為中間字符寞肖，這樣得到的回文子串最長纲酗。
3. 代碼實現(xiàn)
int longestPalindrome(std::string str)
{
char charMap[128] = {0}; // 字符串哈希表
int max_length = 0;
int flag = 0;
for (int i = 0; i < str.size(); i++) {
charMap[str[i]]++;
}
for (int i = 0; i < 128; i++) {
if (charMap[i] % 2 == 0) {
max_length += charMap[i];
}
else {
max_length += charMap[i] - 1;
flag = 1;
}
}
return max_length + flag;
}
詞語模式
1. 題目
給定一個字符串和一個匹配模式，如str = “dog dog great great"和匹配字符串pattern = "aabb"新蟆，那么成str和pattern匹配觅赊，確認給定的字符串和匹配模式是否匹配。
2. 思路
首先琼稻，從字符串中將單詞拆解吮螺，在拆解的過程中同時對pattern進行map映射，并維護一個used數(shù)組用來判斷pattern中的字符是否已經(jīng)使用過了。
在拆解的過程中鸠补，
- 如果拆解的單詞在map中沒有出現(xiàn)過萝风，那么判斷當(dāng)前的pattern對應(yīng)的字符是否使用過，如果使用過就返回false紫岩，如果沒有使用就將該單詞做映射规惰。
- 如果當(dāng)前拆解出的單詞出現(xiàn)過，判斷pattern是否匹配泉蝌，不匹配就返回false
3. 代碼
bool wordPattern(std::string pattern, std::string str)
{
std::map<std::string, char> word_map; // 單詞到pattern的映射表
char used[128] = {0};
std::string word; // 臨時保存拆分出來的單詞
int pos = 0; // 指向pattern
str.push_back(' ');
for (int i = 0; i < str.size(); i++) {
if (str[i] == ' ') { // 遇到空格說明遇到了單詞
if (pos == pattern.length()) { // 到達pattern末尾
return false;
}
// 若單詞未出現(xiàn)在哈希映射中
if (word_map.find(word) == word_map.end()) {
if (used[pattern[pos]]) { // 如果當(dāng)前pattern字符已經(jīng)使用
return false;
}
word_map[word] = pattern[pos];
used[pattern[pos]] = 1;
}
else {
if (word_map[word] != pattern[pos]) {
return false;
}
}
word = "";
pos++;
}
else {
word +=str[i];
}
}
if (pos != pattern.length()) {
return false;
}
return true;
}
同字符詞語分組
1. 題目
已知一組字符串歇万，將其中相同字符組成的單詞放在一起輸出.
2. 思路
得到一個單詞時候，對該單詞進行排序然后用排序后的單詞作為鍵梨与，將原始的單詞作為值進行hash存儲堕花，遇到下一個單詞的時候，對單詞進行排序判斷是否在map中出現(xiàn)過粥鞋，如果沒有則添加新的鍵缘挽，如果存在就直接將該單詞添加到該鍵所對應(yīng)的值數(shù)組里面。
3. 代碼
std::vector<std::vector<std::string>> groupAnagram(std::vector<std::string> &strs)
{
std::map<std::string, std::vector<std::string>> mymap; // 臨時的map
std::vector<std::vector<std::string>> res;
// 遍歷字符串向量
for (auto i : strs) {
std::string temp = i;
std::sort(temp.begin(), temp.end());
if (mymap.find(temp) == mymap.end()) { // 如果在map中
std::vector<std::string> item;
mymap[temp] = item;
}
mymap[temp].push_back(i);
}
// 將hash表中的數(shù)據(jù)呻粹，放入res結(jié)果中
for (auto i: mymap) {
res.push_back(i.second);
}
return res;
}
無重復(fù)字符的最長子串
1. 題目
求給定的字符串中壕曼，無重復(fù)字符的最長子串
2. 思路
考慮在一次遍歷的過程中能夠得到想要的結(jié)果，此時需要使用兩個指針等浊，維護一個滑動窗口腮郊，窗口中的字符串即為我們要求的最長子串。這時問題就變成了怎么維護這個滑動窗口筹燕，兩個指針分別在什么時候移動轧飞，怎么移動；
3. 代碼
int lengthOfLongestSubStirng(std::string str)
{
int begin = 0;
int result = 0;
std::string word = "";
int char_map[128] = {0};
for (int i = 0; i < str.size(); i++) {
char_map[str[i]]++;
if (char_map[str[i]] == 1) { // word中沒有出現(xiàn)過該字符
word += str[i];
if (result < word.length()) {
result = word.length();
}
}
else { // 如果在word中出現(xiàn)過
while (begin < i && char_map[str[i]] > 1) {
char_map[str[begin]]--;
begin++;
}
word = "";
for (int j = begin; j <= i; j++) {
word += str[j];
}
}
}
return result;
}
