时间戳

首页 > 解决方案 > 在列表中查找回文

java - 在列表中查找回文

问题描述

假设我们有一个整数列表，例如：

L = [13,13,4,13,4,2]

我想找到所有回文的集合，其中每个回文都是L包含连续整数的子列表。对于上面的列表，这将是：

S = {[13], [4], [2], [13,13], [13,4,13], [4,13,4]}

因为 的倒数L是L' = [2,4,13,4,13,13]，并且 的每个元素都以正确的顺序S出现。L'

我怎样才能找到所有回文的集合？我幼稚的方法是检查幂集的每个元素是否L出现在 中L'，但这是低效的，我相信有更好的解决方案。

标签： javaalgorithmpalindrome

解决方案

我认为我的解决方案与MC Emperor的解决方案非常相似，但我专注于不创建像列表这样的临时对象。

left我使用和索引选择给定数组的子数组right并检查它的回文。

public static Set<List<Integer>> findAllPalindromes(int[] arr) {
    Set<List<Integer>> res = new LinkedHashSet<>();

    for (int length = 1; length < arr.length; length++)
        for (int left = 0, right = left + length - 1; right < arr.length; left++, right++)
            if (isPalindrome(arr, left, right))
                res.add(sublist(arr, left, right));

    return res;
}

此方法检查是否给定子数组回文：

private static boolean isPalindrome(int[] arr, int left, int right) {
    for (; left < right; left++, right--)
        if (arr[left] != arr[right])
            return false;

    return true;
}

此方法为给定的子数组创建单独的列表：

private static List<Integer> sublist(int[] arr, int left, int right) {
    List<Integer> res = new ArrayList<>(right - left);

    for (; left <= right; left++)
        res.add(arr[left]);

    return res;
}

推荐阅读