MyLeetcode/cpp_solutions/2131.cpp at main · Kaminyou/MyLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        unordered_map<string, int> mp;
        bool sameFlag = false;
        for (auto word : words) {
            mp[word]++;
        }
        int res = 0;
        unordered_set<string> st;
        bool flag = false;
        for (auto word : words) {
            if (st.find(word) != st.end()) continue;
            string wordReversed = word;
            reverse(wordReversed.begin(), wordReversed.end());
            int count = min(mp[word], mp[wordReversed]);
            if (word == wordReversed) {
                if (count & 1) flag = true;
                res += (count / 2) * 4;
            }
            else res += count * 4;
            st.insert(word);
            st.insert(wordReversed);
        }

        return res + flag * 2;
    }
};

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        vector<int> hash(26 * 26, 0);
        for (auto& word : words) {
            int key = (word[0] - 'a') * 26 + (word[1] - 'a');
            hash[key]++;
        }
        bool flag = false;
        int cnt = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (i == j) {
                    if (hash[i * 26 + j]) {
                        if (hash[i * 26 + j] & 1) {
                            flag = true;
                        }
                        cnt += hash[i * 26 + j] / 2;
                    }
                }
                else {
                    cnt += min(hash[i * 26 + j], hash[j * 26 + i]);
                }
            }
        }
        return cnt * 4 + flag * 2;
    }
};