leetcode每日一题 -- 2131.连接两字母单词得到的最长回文串

思路

说实话,一开始没啥思路,于是看了评论区,以下是从评论区大佬代码中得到的思路

题意:

• 串都是两个字母的,所以要构成回文串有三种情况 -- ab和ba配对,放在对应位置 ; aa和aa配对,放在对应位置 ; aa单独放在中间位置

于是,可以采用 "先记录,后配对,配对完即消除" 的方式,最后判断是否还有aa型的串

• 其中,记录可以使用哈希表 -- key={a,b},value=出现次数 ; 也可以使用二维数组[a][b]
• 配对的时候,假设当前为ab型串(当然,a可以等于b),去配对ba型串
• 找到了,就将原串出现次数-1 (对应消除) ; 找不到,记录当前ab串

代码

class Solution {
public:int longestPalindrome(vector<string>& words) {// 哈希表 map[a][b]表示ab串是否在数组中存在int map[26][26] = {};int res = 0;for (auto it : words) {int a = it[0] - 'a', b = it[1] - 'a';if (map[b][a]) {res += 4; // 2个两字母单词map[b][a]--;} else {map[a][b]++;}}for (int i = 0; i < 26; ++i) {if (map[i][i]) {res += 2; // 只取出一对aa型,放在结果串的中间break;}}return res;}
};