面试题 08.07. 无重复字符串的排列组合

面试题 08.07. 无重复字符串的排列组合

无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。

示例1:

 输入:S = "qwe"
 输出:["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例2:

 输入:S = "ab"
 输出:["ab", "ba"]

提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

代码如下:

class Solution {
    /**
     * @param String $S
     * @return String[]
     */
    function permutation($S) {
        $sArr = str_split($S);
        $sKey = array_keys($sArr);
        $res = $this->permute($sKey);
        $result = [];
        foreach ($res as $key => $items) {
            $temp = '';
            foreach ($items as $ky => $item) $temp .= $sArr[$item];
            $result[] = $temp;
        }
        return $result;
    }

    function permute($nums){
        $count = count($nums);
        if ($count == 1) return [$nums];
        $last = $x = $count - 1;
        $result[] = $nums;
        while (true) {
            $y = $x--;
            if ($nums[$x] < $nums[$y]) {
                $z = $last;
                while ($nums[$x] > $nums[$z]) $z--;
                list($nums[$x], $nums[$z]) = array($nums[$z], $nums[$x]);
                for ($i = $last; $i > $y; $i--, $y++) {
                    list($nums[$i], $nums[$y]) = array($nums[$y], $nums[$i]);
                }
                $x = $last;
                $result[] = $nums;
            }
            if ($x == 0) break;
        }
        return $result;
    }
}

本文链接:https://itarvin.com/detail-216.aspx

登录或者注册以便发表评论

登录

注册