131.md

✏️Leetcode基础刷题之(131. Palindrome Partitioning)

2019-08-26 吴亲库里 库里的深夜食堂

---

✏️描述

拆分回文串，给定一个字符串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;
    }

---

联系

​