面试题 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;
}
}