TyranitarX Connect.

LeetCode每日打卡-2020.8.6

算法
Word count: 667Reading time: 3 min
2020/08/06 Share

2020.8.6 每日题解 LeetCode 336. 回文对

给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1：

1
2
3
输入：["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]] 
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2：

1
2
3
输入：["bat","tab","cat"]
输出：[[0,1],[1,0]] 
解释：可拼接成的回文串为 ["battab","tabbat"]

思路详解

对于组合起来的两个字符串可以
分为words[i].length>=words[j].length
与words[i].length<words[j].length

在这里我们认为所取字符串为长串则有以下三种情况。
1、字符串本身的翻转在整个输入单词组中（可以放在下方两种情况中，即前缀/后缀为空串）
2、字符串前缀为回文串，剩余后缀的翻转在单词组中，拼接在字符串前部
3、字符串后缀为回文串，剩余前缀的翻转在单词组中，拼接在字符串后补

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.*;

public class H336_palindromePairs {
    //暴力（超时）
    public List<List<Integer>> palindromePairsForce(String[] words) {
        List<List<Integer>> returnList = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                List<Integer> list = new ArrayList<>();
                String add = words[i] + words[j];
                if (isPalindrome(add) && i != j) {
                    list.add(i);
                    list.add(j);
                    returnList.add(list);
                }
            }
        }
        return returnList;
    }

    public boolean isPalindrome(String s) {
        if (s.equals(""))
            return true;
        String[] ss = s.split("");
        boolean judge = true;

        for (int i = 0; i < (s.length() / 2); i++) {
            if (!ss[i].equals(ss[ss.length - i - 1]))
                judge = false;
        }
        return judge;
    }

    //哈希表查找
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> reversemap = new HashMap<>();
        // 将翻转后的字符串加入hashmap中
		for (int i = 0; i < words.length; i++) {
            reversemap.put(new StringBuilder(words[i]).reverse().toString(), i);
        }
		//利用set防止前缀后缀空重复
        Set<List<Integer>> nodelist = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
			//将字符串拆分为前缀后缀两部分
            for (int j = 0; j <= word.length(); j++) {
                String left = word.substring(j);
                String right = word.substring(0, j);
				//后缀回文情况
                if (isPalindrome(left)) {
                    List<Integer> list = new ArrayList<>();
                    if (reversemap.containsKey(right) && i != reversemap.get(right)) {
                        list.add(i);
                        list.add(reversemap.get(right));
                        nodelist.add(list);
                    }
                }
				//前缀回文情况
                if (isPalindrome(right)) {
                    if (reversemap.containsKey(left) && i != reversemap.get(left)) {
                        List<Integer> list = new ArrayList<>();
                        list.add(reversemap.get(left));
                        list.add(i);
                        nodelist.add(list);
                    }
                }

            }
        }
        return new ArrayList<>(nodelist);
    }
}

Author：TyranitarX

原文链接：http://tyranitarx.github.io/2020/08/06/LeetCode%E6%AF%8F%E6%97%A5%E6%89%93%E5%8D%A1-2020-8-6/

发表日期：August 6th 2020, 4:48:52 pm

更新日期：August 11th 2020, 10:14:06 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 2020.8.6 每日题解 LeetCode 336. 回文对
    1. 1.0.1. 思路详解
Total : 20
2020
2019
machine learning deep learning TensorFlow 前端 算法