Leetcode基础刷题之PHP解析(131. Palindrome Partitioning)


2019-8-26 星期一 开始吧

上一题链接Leetcode基础刷题之PHP解析(130. Surrounded Regions)


b43cfe1b436e53d44ad2ed2d68692ed3.png


题目描述

拆分回文串,给定一个字符串S,返回所有可能的分区回文字符串,也就是说最小的单位就是一个字符串也是回文字符串。


题目分析

返回所有的,意味我们需要遍历所有的组合情况,从一个字符串判断回文到长度等于整个字符串的回文判断 ,可以采取DFS,具体用递归实现。还需要额外的一个函数,用来判断当前截取的字符串是否是回文。用两个变量,一个用来存储最终结果,另一个用来保存遍历的每一个组合,每次把组合里的值进行回文判断,比如可以左 右进行判断,如果没有问题,就可以把当前这个组合加入到最终变量中,作为结果中的一组。
代码实现
    /**
     * @param String $s
     * @return String[][]
     */
    function partition($s) {
        $out=[];
        $res=[];
        $this->helper($s,0,$out,$res);
        return $res;
    }
    
    function helper($s,$start,&$out,&$res)
    {
        if($start==strlen($s)){
            $res[]=$out; 
            return;
        } 
        for($i=$start;$i<strlen($s);++$i){
           if(!$this->isPalindrome($s,$start,$i)) continue;
            array_push($out,substr($s,$start,$i-$start+1));
            $this->helper($s,$i+1,$out,$res);
            array_pop($out);//恢复out
        }
    }
    
    function isPalindrome($s,$start,$end){
        while($start<$end){
            if($s[$start] != $s[$end]) return false;
           ++$start;
            --$end;
        }
        return true;
    }


点赞 取消点赞 收藏 取消收藏

<< 上一篇: Leetcode PHP题解--D116 409. Longest Palindrome

>> 下一篇: Leetcode基础刷题之PHP解析(134. Gas Station)