點擊上方「程式設計師大白」，選擇「星標」公眾號
重磅乾貨，第一時間送達
題目分析：給定一個字符串數組words，無重複字符串。問：有多少對不同的(i, j)滿足words[i]+words[j]是回文串？
解題思路（1）暴力枚舉(i, j)，判斷words[i]+words[j]是否是回文串。時間複雜度為O(n^2*k)。
解題思路（2）將所有字符串逆序插入map。對於每個字符串s，枚舉分割點pos，滿足[pos ~ s.size()-1]是回文串，且[0 ~ pos-1]的逆串在map中存在。時間複雜度為O(n*K)。
算法的正確性：思路1無需舉例。對於思路2，如words = ["bat", "tab", "cat"]， 則map["tab"] = 0, map["bat"] = 1, map["tac"] = 2, 對於"bat", 我們發現map["bat"] = 1，且末尾串""為回文串。則(0, 1)為一解；對於"bat", 我們發現map["tab"] = 0，且末尾串""為回文串。則(1, 0)為一解。故答案為[[0, 1], [1, 0]]。
解法一
class Solution {
public:
bool judge(string& a, string& b){
int i = 0, j = b.size()-1;
while(i < a.size()&&j >= 0&&a[i] == b[j]) i++, j--;
if(i < a.size()&&j >= 0) return false;
if(j < 0){
j = a.size()-1;
while(i < j&&a[i] == a[j]) i++, j--;
return i >= j;
}
else{
i = 0;
while(i < j&&b[i] == b[j]) i++, j--;
return i >= j;
}
}
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> ans;
for(int i = 0; i < words.size(); i++)
for(int j = 0; j < words.size(); j++)
if(i != j&&judge(words[i], words[j]))
ans.push_back({i, j});
return ans;
}
};
解法二
class Solution {
public:
bool judge(string& str){
int i = 0, j = str.size() - 1;
while(i < j)
if(str[i++] != str[j--]) return false;
return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> ma;
vector<vector<int>> ans;
for(int i = 0; i < words.size(); i++)
ma[{words[i].rbegin(), words[i].rend()}] = i;
if(ma.find("") != ma.end()){
for(int i = 0, k = ma[""]; i < words.size(); i++)
if(words[i] != ""&&judge(words[i]))
ans.push_back({k, i});
}
for(int i = 0; i < words.size(); i++) {
for(int j = 0; j < words[i].size(); j++) {
string l = words[i].substr(0, j), r = words[i].substr(j, words[i].size()-j);
if(ma.find(l) != ma.end()&&judge(r)&&ma[l] != i)
ans.push_back({i, ma[l]});
if(ma.find(r) != ma.end()&&judge(l)&&ma[r] != i)
ans.push_back({ma[r], i});
}
}
return ans;
}
};
重磅！程式設計師大白交流群-學術微信交流群已成立
額外贈送福利資源！邱錫鵬深度學習與神經網絡，pytorch官方中文教程，利用Python進行數據分析，機器學習學習筆記，pandas官方文檔中文版，effective java（中文版）等20項福利資源
獲取方式：進入群後點開群公告即可領取下載連結
注意：請大家添加時修改備註為 [學校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對話系統。
號主，微商請自覺繞道。謝謝！
推薦閱讀
5款Chrome插件，第1款絕對良心！
為開發色情遊戲，這家公司赴日尋找AV女優拍攝，期望暴力賺錢結果...
拼多多終於釀成慘劇
華為阿里下班時間曝光：所有的光鮮，都有加班的味道
成都天府軟體園，一個程式設計師跳樓了……
關於程式設計師大白
程式設計師大白是一群哈工大，東北大學，西湖大學和上海交通大學的碩士博士運營維護的號，大家樂於分享高質量文章，喜歡總結知識，歡迎關注[程式設計師大白]，大家一起學習進步！