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

2019-8-26 星期一 开始吧

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

题目描述

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

题目分析

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