131. 分割回文串

题意：

思路：

s****start** i
aab****0*****0 a 
aab****1*****1 a 
aab****2*****2 b 
aab****1*****2 
aab****0*****1 aa 
aab****2*****2 b 
aab****0*****2

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @return String[][]
     */
    public $res = [];
    function partition($s) {
        $this->do($s, 0, []);
        return $this->res;
    }
    function do($s, $start, $array) {
        //递归出口，空字符串
        if ($start == strlen($s)) {
            $this->res[] = $array;
            return;
        }
        for ($i = $start; $i < strlen($s); $i++) {
            if (!$this->isPalindrome($s, $start, $i)) continue;
            array_push($array, substr($s, $start, $i - $start + 1));
            $this->do($s, $i + 1, $array);
            array_pop($array);
        }
    }
    function isPalindrome($s, $start, $end) {
        while ($start < $end) {
            if ($s[$start] != $s[$end]) return false;
            ++$start;
            --$end;
        }
        return true;
    }
}

GO代码实现：

func partition(s string) [][]string {
    array := [][]string{}
    res := []string{}
    dfs(s, 0, res, &array)
    return array
}
func dfs(s string, start int, res []string, array *[][]string) {
    if start == len(s) {
        tmp := make([]string, len(res))
        copy(tmp, res)
        *array = append(*array, tmp)
        return
    }
    for i := start; i < len(s); i++ {
        // start-i之间不是回文时continue
        if !isPal(s, start, i) {
            continue
        }
        res = append(res, string(s[start:i+1]))
        dfs(s, i+1, res, array)
        res = res[:len(res)-1]
    }
}
func isPal(s string, l, r int) bool {
    for l < r {
        if s[l] != s[r] {
            return false
        }
        l, r = l+1, r-1
    }
    return true
}