문제

Codewars

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

문자열이 인자로 주어질 때 중복 없는 모든 문자열 순열을 구하라.

Examples:

permutations('a'); // ['a']
permutations('ab'); // ['ab', 'ba']
permutations('aabb'); // ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

 

LeetCode

Given a collection of distinct integers, return all possible permutations.

값이 다른 정수 배열이 주어질 때 모든 배열 순열을 구하라.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

 

풀이

주어진 인자로 조합 가능한 모든 경우의 수를 찾기 위해서
1. 앞에서 부터 순회 하며 first 변수에 담아두고
2. slice로 원본 배열을 복사 하고 splice 메소드를 사용해 (splice는 원본 배열 변형시킴)
3. first를 제외한 값들을 새로운 배열로 만들어
4. base case인 인자 값이 길이가 2 이하로 작아질 때까지 1번 부터 다시 재귀를 돌린다.

위의 사항은 인자 타입에 순열을 찾을 때 필수적인 조건들이다.
따라서 배열 메소드인 slice, splice을 사용하기 위해서는 어떤 타입의 인자이던 일단 배열로 바꾸어 실행해야 함.

제출 코드

Codewars - String permutation

Codewars 문제에서는 문자열이 주어졌기 때문에 early return 이후에 곧바로 split 으로 배열로 변경했다.
그리고 중복을 없애기 위해 result.indexOf(first + combination[j]) < 0 조건을 추가하였다.

function permutations(str) {
  var result = [];

  if (str.length === 1) return [str];
  if (str.length === 2) {
    return str[0] === str[1] 
      ? [str] 
      : [str, str[1] + str[0]];
  }

  var arr = str.split('');

  for (var i = 0; i < arr.length; i++) {
    var first = arr[i];
    var sub = arr.slice();
    sub.splice(i, 1);

    var combination = permutations(sub.join(''));

    for (var j = 0; j < combination.length; j++) {
      if (result.indexOf(first + combination[j]) < 0) {      
        result.push(first + combination[j]);
      }
    }
  }

  return result;
}

 

LeetCode - Array permutation

문제에 distinct integers이 주어진다 하여 중복 체크는 따로 안하고 concat 메소드 사용으로 배열을 합쳐 반환했다.

const permute = arr => {
  var result = [];

  if (arr.length === 1) return [arr];
  if (arr.length === 2) return [arr, [arr[1], arr[0]]];

  for (var i = 0; i < arr.length; i++) {
    var first = arr[i];
    var sub = arr.slice();
    sub.splice(i, 1);

    var combination = permute(sub);
    for (var j = 0; j < combination.length; j++) {
        result.push([].concat(first, combination[j]));
    }
  }

  return result;
};

 

---

permutation은 인자의 타입이 무엇이던 하나의 캐릭터씩 순서대로 순회 + 나머지 값들을 재귀하는 개념은 크게 달라지지 않는다.