双周赛第69场:LeetCode:5962.连接单词得到的最长回文串

浏览次数 : 9370 次 2022-01-09

博文字数统计 : 1.6k字 | 阅读所需时长 : 6分

× 文章目录

1. 双周赛第69场：LeetCode：5962.连接单词得到的最长回文串

双周赛第69场：LeetCode：5962.连接单词得到的最长回文串
- 时间：2022-01-09
- 力扣难度：Medium
- 个人难度：Medium
- 数据结构：哈希表、字符串
- 算法：哈希计数

双周赛第69场：LeetCode：5962.连接单词得到的最长回文串

1. 题目描述

题目：原题链接
- 给你一个字符串数组 words，words 中每个元素都是一个包含两个小写英文字母的单词。
- 请你从 words 中选择一些元素并按任意顺序连接它们，并得到一个尽可能长的回文串，回文串指的是从前往后和从后往前读一样的字符串。
- 每个元素至多只能使用一次，请你返回你能得到的最长回文串的长度。
- 如果没办法得到任何一个回文串，请你返回 0 。
- 注意：每一个word都是两个小写字母
输入输出规范
- 输入：字符串数组words
- 输出：最长的回文串的长度
输入输出示例
- 输入：words = [“ab”,”ty”,”yt”,”lc”,”cl”,”ab”]
- 输出：8

2. 方法：哈希计数+奇偶分析

思路：哈希计数+奇偶分析
- 根据题意可知，字符串数组中，存在两种类型的单词，同时，单词可能会重复，所以需要进行计数，注意单词均为两个小写字母，这可以简化计数方式
  - 本身就是回文串的单词，如：aa，对于这种类型，可以使用new int[26]数组来进行哈希计数
  - 本身不是回文串的单词，如：ab，对于这种类型，可以使用Map来计数
  - 此外，还可以通过二维数组int[26][26]来计数，本题解没有使用这种方式，感兴趣的可以尝试下
- 除此之外，本题需要根据单词是否回文串分类讨论
- 情况一：回文串单词，此时需要先进行哈希计数(第一次遍历)，之后再根据每个存在的单词的个数的奇偶性进行讨论(第二次遍历)
  - 个数为偶数时：可以对称的放到最终的最长回文串的两侧，即此时总长度满足len += count * 2
  - 个数为奇数时：可以对称的将小于该奇数的最大偶数对称放在两侧，同样有len += (count - 1) * 2，并且额外多出来的一个回文单词，可以放在最长回文串的正中间，即len += 2
- 情况二：非回文串单词，此时可以在进行哈希计数的同时，判断该单词的逆序单词是否存在于哈希表中(一次遍历)
  - 存在时可以将其分别放于最长回文串的两侧，有len += 4
  - 不存在时将当前单词放入哈希表，等待验证后续单词是否会与其匹配
![
- 判断单词是否回文的方式可以借助StringBuilder的reverse()方法
复杂度分析：n 是字符串数组的长度，即单词个数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

题解

public int longestPalindrome(String[] words) {
    if (words == null || words.length == 0) return 0;
    Map<String, Integer> wordMap = new HashMap<>(); // 存放不是回文串的word
    int[] hash = new int[26];
    int palindromeLen = 0;
    String reverse = "";
    for (String word : words) {
        StringBuilder sb = new StringBuilder();
        reverse = sb.append(word).reverse().toString();
        // 分类讨论，本身就是回文串的word，直接计入最长回文串
        if (word.equals(reverse)) { //  if (word.charAt(0) == word.charAt(1))
            hash[word.charAt(0) - 'a']++;
        } else {
            // 本身不是回文串的word，去匹配对应的reverse结构
            if (wordMap.get(reverse) != null && wordMap.get(reverse) > 0) {
                // 匹配成功，可以添加到最长回文串的两端，len + 2 * len(word)
                palindromeLen += 4;
                wordMap.put(reverse, wordMap.get(reverse) - 1);
            } else {
                // 匹配失败，将当前word加入wordMap
                wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
            }
        }
    }
    boolean last = false;
    for (int count : hash) {
        if ((count & 1) == 0) {
            palindromeLen += 2 * count; // word.length()
        } else {
            palindromeLen += 2 * (count - 1); // word.length()
            last = true;
        }
    }
    if(last) palindromeLen += 2;
    return palindromeLen;
}

3. 方法二：优化

思考与优化
- 思考：本题的输入具有一定的限制
  - 限制一：单词都是两个字母
  - 限制二：单词都是小写字母
- 优化
  - 对于限制一，此时对放在正中间的回文单词没有要求，如果单词的字母个数没有限制的话，如：a、cc、sss，此时放在正中间的应该是最长的回文单词
  - 对于限制二，此时可以使用数组哈希，如果单词可以有大小写字母甚至一些其他符号，此时应该使用键值对哈希
复杂度分析：n 是字符串数组的长度，即单词个数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

题解

public int longestPalindrome(String[] words) {
    if (words == null || words.length == 0) return 0;
    Map<String, Integer> wordMap = new HashMap<>(); // 存放不是回文串的word
    Map<String, Integer> palindromeMap = new HashMap<>(); // 存放是回文串的word
    int palindromeLen = 0;
    String reverse = "";
    for (String word : words) {
        StringBuilder sb = new StringBuilder();
        reverse = sb.append(word).reverse().toString();
        // 分类讨论，本身就是回文串的word，直接添加到map中，后面在进行分析
        if (word.equals(reverse)) { //  if (word.charAt(0) == word.charAt(1))
            palindromeMap.put(word, palindromeMap.getOrDefault(word, 0) + 1);
        } else {
            // 本身不是回文串的word，去匹配对应的reverse结构
            if (wordMap.get(reverse) != null && wordMap.get(reverse) > 0) {
                // 匹配成功，可以添加到最长回文串的两端，len + 2 * len(word)
                palindromeLen += word.length() << 1;
                wordMap.put(reverse, wordMap.get(reverse) - 1);
            } else {
                // 匹配失败，将当前word加入wordMap
                wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
            }
        }
    }

    // 分析回文word的情况，对应palindromeMap
    int maxSingleLen = 0;
    Set<Map.Entry<String, Integer>> wordEntries = palindromeMap.entrySet();
    for (Map.Entry<String, Integer> wordEntry : wordEntries) {
        // 偶数个回文word，直接全部计入最长回文串长度中
        if ((wordEntry.getValue() & 1) == 0) {
            palindromeLen += wordEntry.getKey().length() * wordEntry.getValue();
        }else {
            // 奇数个回文word，只能直接将(count - 1)个word计入最长回文串长度中，最后一个与其他单独的word进行长度比较，选择最长的
            palindromeLen += wordEntry.getKey().length() * (wordEntry.getValue() - 1);
            maxSingleLen = Math.max(maxSingleLen, wordEntry.getKey().length());
        }
    }
    // 将选择的最长的单个回文word计入最长回文串长度中
    palindromeLen += maxSingleLen;
    return palindromeLen;
}

本文作者： Chthollists
发布时间： 2022-01-09 19:35:21
最后更新： 2022-01-27 20:44:38
本文标题： 双周赛第69场:LeetCode:5962.连接单词得到的最长回文串
本文链接： https://chthollists.github.io/post/2b3f8bdc.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！