开发者社区> 楚兴> 正文

[LeetCode] Palindrome Pairs

简介: Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome. Example 1:
+关注继续查看

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

解题思路

首先想到的是暴力组合,分别检验所有组合是否为回文,该方法提交后超时,暴力代码如下:

//Time Limit Exceeded
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> indices = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (j == i) {
                    continue;
                } else {
                    String temp = words[i] + words[j];
                    if (isPalindrome(temp)) {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        list.add(j);
                        indices.add(list);
                    }
                }
            }
        }
        return indices;
    }

    private boolean isPalindrome(String word) {
        for (int i = 0, j = word.length() - 1; i < j; i++, j--) {
            if (word.charAt(i) != word.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

于是想到另一种思路:

  1. 对于空字符串,如果数组中有回文字符串,则将空字符串与回文字符串进行组合。
  2. 对于非空字符串,将其进行拆分,如果其中一段为回文,并且数组中可以找到另一段的逆序字符串,则说明可以组合为回文。
    例如:”sssll” = “ss” + “sll”,而且数组中存在”lls”,因此组合”lls”和”sssll”。

注意:组合两个字符串时,需要注意顺序问题。如果字符串前半段为回文,则另一个字符串需要组合在前面;如果字符串后半段为回文,则另一个字符串需要组合在后面。

实现代码

//Runtime: 247 ms
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        List<List<Integer>> indices = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].length() == 0) {
                for (Map.Entry<String, Integer> entry : map.entrySet()) {
                    if (isPalindrome(entry.getKey())) {
                        addAll(indices, i, entry.getValue());
                    }
                }
            }

            for (int j = 0; j < words[i].length(); j++) {
                String front = words[i].substring(0, j);
                String back = words[i].substring(j, words[i].length());
                String rfront = reverse(front);
                String rback = reverse(back);
                if (isPalindrome(front) && map.containsKey(rback)) {
                    addAll(indices, map.get(rback), i);
                }
                if (isPalindrome(back) && map.containsKey(rfront)) {
                    addAll(indices, i, map.get(rfront));
                }
            }
        }
        return indices;
    }

    private void addAll(List<List<Integer>> indices, int a, int b) {
        if (a == b) {
            return;
        }
        List<Integer> list = new ArrayList<>();
        list.add(a);
        list.add(b);
        indices.add(list);
    }

    private String reverse(String word) {
        return new StringBuilder(word).reverse().toString();
    }

    private boolean isPalindrome(String word) {
        for (int i = 0, j = word.length() - 1; i < j; i++, j--) {
            if (word.charAt(i) != word.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
9162 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
12612 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
18063 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
17050 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
24836 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
21553 0
+关注
楚兴
达则兼济天下,穷则独善其身。
344
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载