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

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2412 views 0 likes 0 collects

2019-8-26 星期一开始吧

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

题目描述

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

题目分析

返回所有的，意味我们需要遍历所有的组合情况，从一个字符串判断回文到长度等于整个字符串的回文判断，可以采取DFS，具体用递归实现。还需要额外的一个函数，用来判断当前截取的字符串是否是回文。用两个变量，一个用来存储最终结果，另一个用来保存遍历的每一个组合，每次把组合里的值进行回文判断，比如可以左右进行判断，如果没有问题，就可以把当前这个组合加入到最终变量中，作为结果中的一组。
代码实现

xxxxxxxxxx
 
/**
     * @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;
    }