首页 > 其他分享 >【DFS】LeetCode 131. 分割回文串

【DFS】LeetCode 131. 分割回文串

时间:2023-03-02 12:34:13浏览次数:51  
标签:index right temp int DFS 131 len array LeetCode

题目链接

131. 分割回文串

思路

使用 DFS,同时依次检查分割的字符串是否是回文串。

注意:需要频繁添加删除末尾元素时,可以使用 Deque

代码

class Solution {
    private List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        int len = s.length();
        Deque<String> temp = new ArrayDeque<>();
        char[] array = s.toCharArray();

        dfs(array, 0, len, temp);

        return result;
    }

    private void dfs(char[] array, int index, int len, Deque<String> temp) {
        if(index == len){
            result.add(new ArrayList<>(temp));
            return;
        }

        for(int i = index; i < len; i++){
            if(checkPalindrome(array, index, i)){
                temp.add(new String(array, index, i - index + 1));
                dfs(array, i + 1, len, temp);
                temp.removeLast();
            }
        }
    }

    private boolean checkPalindrome(char[] s, int left, int right){
        while(left < right){
            if(s[left] != s[right]){
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

标签:index,right,temp,int,DFS,131,len,array,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17171378.html

相关文章

  • Leetcode——二分法bisect_left,bisect_right
    !前提——列表有序case1如果列表中没有元素x,那么bisect_left(ls,x)和bisec_right(ls,x)返回相同的值,该值是x在ls中“合适的插入点索引,使得数组有序”。此时,ls[index2]......
  • HDFS数据安全与隐私保护
    一、HDFSTrash垃圾桶1.文件系统垃圾桶背景HDFS本身也是一个文件系统,那么就会涉及到文件数据的删除操作。默认情况下,HDFS中是没有回收站垃圾桶概念的,删除操作的数据将......
  • hdfs file system shell的简单使用
    1、背景此处我们通过命令行,简单的学习一下hdfsfilesystemshell的一些操作。2、hdfsfilesystemshell命令有哪些我们可以通过如下网址https://hadoop.apache.org/d......
  • hdfs file system shell的简单使用
    目录1、背景2、hdfsfilesystemshell命令有哪些3、确定shell操作的是哪个文件系统4、本地准备如下文件5、hdfsfilesystemshell5.1mkdir创建目录5.2put上传文件5.3l......
  • HDFS NameNode元数据管理
    一、什么是元数据在HDFS中,元数据主要指的是文件相关的元数据,由NameNode管理维护。从广义的角度来说,因为NameNode还需要管理众多DataNode节点,因此DataNode的位置和健康状......
  • LeetCode算法训练-贪心算法 455.分发饼干 376. 摆动序列 53. 最大子序和
    欢迎关注个人公众号:爱喝可可牛奶LeetCode算法训练-贪心算法455.分发饼干376.摆动序列53.最大子序和前置知识贪心算法核心是找局部最优解,通过局部最优推导出全局最......
  • fastdfs常用配置及命令
    查看确认storage是否自动注册到tracker中:fdfs_monitor/etc/fdfs/storage.conf查看集群情况,对应的storage节点状态:fdfs_monitor/etc/fdfs/client.conffastdfs配置详细说......
  • LeetCode 84. 柱状图中最大的矩形()
    原题解题目约束题解方法一classSolution{public:intlargestRectangleArea(vector<int>&heights){intn=heights.size();vec......
  • LeetCode算法训练-回溯总结
    欢迎关注个人公众号:爱喝可可牛奶LeetCode算法训练-回溯总结适用问题组合问题:N个数里面按一定规则找出k个数的集合排列问题:N个数按一定规则全排列,有几种排列方式切割问......
  • LeetCode算法训练-回溯总结
    欢迎关注个人公众号:爱喝可可牛奶LeetCode算法训练-回溯总结适用问题组合问题:N个数里面按一定规则找出k个数的集合排列问题:N个数按一定规则全排列,有几种排列方式切割......