leetCode：1079. Letter Tile Possibilities

leetCodeの「1079. Letter Tile Possibilities」を解いた。
https://leetcode.com/problems/letter-tile-possibilities/

典型的なバックトラッキングの問題で、今後の参考になりそうなので、解法をここに残しておく。

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int numTilePossibilities(String tiles) {
        if (tiles == null || tiles.length() == 0) {
            return 0;
        }

        // 結果格納用のSet
        Set<String> results = new HashSet<>();

        // 現在訪問中の index の Set
        Set<Integer> visitings = new HashSet<>();

        getResults(tiles, "", results, visitings);
        return results.size();
    }

    // 現在の文字列 curStr の長さが 0 より大きかったら、結果セットに追加。そして、次に進む。
    private void getResults(String tiles, String curStr, Set<String> results, Set<Integer> visitings) {
        if (curStr.length() > 0) {
            results.add(curStr);
        }
        for (int i = 0; i < tiles.length(); i++) {
            // 既に訪問中のものはスキップする。
            if (visitings.contains(i)) {
                continue;
            }

            // 現在のインデックス i を「訪問中」に追加
            visitings.add(i);

            // 次に進む
            getResults(tiles, curStr + tiles.charAt(i), results, visitings);

            // 現在のインデックス i を「訪問中」に削除 (バックトラッキング)
            visitings.remove(i);
        }
    }