[LeetCode] 1079. Letter Tile Possibilities

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

leetcode - Letter Tile Possibilities

문제 유형: 백트래킹

문제 난이도: Medium

 

문제

You have n  tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

 

n개의 타일이 주어지고, tiles[i]에 한 글자가 있다.

모든 가능한 글자들의 길이가 1 이상인 순열들을 구하시오.

 

풀이

백트래킹을 이용해서 모든 경우의 수를 만들고, 해시맵 또는 해시셋을 이요해서 중복제거를 한 자료구조의 크기를 반환하면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
private:
    unordered_set<string> us;
public:
    void dfs(vector<bool>& visited, string subseq, const string& tiles) {
        if(subseq.size() == tiles.size()) {
            return;
        }

        for(int i = 0; i < tiles.size(); ++i) {
            if(!visited[i]) {
                subseq.push_back(tiles[i]);
                us.insert(subseq);
                visited[i] = true;
                dfs(visited, subseq, tiles);
                subseq.pop_back();
                visited[i] = false;
            }
        }
    }
    int numTilePossibilities(string tiles) {
        sort(tiles.begin(), tiles.end());
        vector<bool> visited(tiles.size(), false);
        dfs(visited, "", tiles);
        return us.size();
    }
};

 

Go

var mp map[string]int
var n int

func dfs(visited []bool, s, tiles string) {
    if len(s) == n {
        return
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            temp := s + string(tiles[i])
            mp[temp]++
            visited[i] = true
            dfs(visited, temp, tiles)
            visited[i] = false
        }
    }
}

func numTilePossibilities(tiles string) int {
    mp = make(map[string]int)
    n = len(tiles)
    visited := make([]bool, n)
    dfs(visited, "", tiles)
    return len(mp)
}