题解 | #所有的回文子串II# Java

所有的回文子串II

https://www.nowcoder.com/practice/3373d8924d0e441987650194347d3c53

解法1 暴力遍历

public class Solution {

    public String[] partitionII (String s) {
        HashSet<String> set = new HashSet<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    set.add(s.substring(i, j + 1));
                }
            }
        }
        String[] ans = new String[set.size()];
        int idx = 0;
        for (String si : set) {
            ans[idx++] = si;
        }
        Arrays.sort(ans);
        return ans;
    }

    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) return false;
        }
        return true;
    }
}

解法2 对于每个字符或相邻两个字符作为中心,向左右扩展来找到回文子串。

public class Solution {

    public String[] partitionII (String s) {
        HashSet<String> set = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            expandAroundCenter(s, i, i, set);
            expandAroundCenter(s, i, i + 1, set);
        }
        String[] ans = new String[set.size()];
        int idx = 0;
        for (String si : set) {
            ans[idx++] = si;
        }
        Arrays.sort(ans);
        return ans;

    }

    private void expandAroundCenter(String s, int left, int right,
                                    HashSet<String> set) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            if (right + 1 - left > 1) set.add(s.substring(left, right + 1));
            left--;
            right++;
        }
    }
}

算法题刷刷刷 文章被收录于专栏

数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序

全部评论

相关推荐

点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务