[Leetcode 8/100] Letter Tile Possibilities - Medium

https://leetcode.com/problems/letter-tile-possibilities/

Letter Tile Possibilities - LeetCode

백트래킹 문제로 DFS를 이용해 조합을 구하면 되는 문제입니다.

이런 유형의 문제는 쉽게 접해볼 수 있었는데 문자열을 다루는 부분이 조금 어려웠습니다.

StringBuilder의 setLength 함수를 통해 원래의 문자열로 되돌려주는 부분이 가장 중요했던 것 같습니다.

class Solution {

        Set<String> set = new HashSet();
        boolean[] check;
        public int numTilePossibilities(String tiles) {

            StringBuilder sb = new StringBuilder();
            check = new boolean[tiles.length()];
            DFS(sb, tiles);
            return set.size();
        }

        public void DFS(StringBuilder sb, String tiles){
            if(sb.length() > tiles.length()) return;
            if(sb.length() >= 1) set.add(sb.toString());

            for(int i=0; i<tiles.length(); i++){
                if (check[i] == true) continue;
                check[i] = true;
                int length = sb.length();
                DFS(sb.append(tiles.charAt(i)), tiles);
                sb.setLength(length);
                check[i] = false;
            }
        }

    }