回溯解法,JAVA:
public final int numTilePossibilities(String tiles) { Set<String> set = new HashSet<String>(); search(tiles.toCharArray(), "", tiles.length(), set); return set.size(); } public final void search(char[] chars, String ans, int len, Set<String> set) { if (len < 0) return; for (int i = 0; i < chars.length; i++) { if (chars[i] == '0') continue; char his = chars[i]; chars[i] = '0'; String next = ans + his; if (!set.contains(next)) set.add(next); search(chars, next, len - 1, set); chars[i] = his; } }
JS:
/** * @param {string} tiles * @return {number} */ var numTilePossibilities = function (tiles) { let mySet = new Set(); search(tiles.split(""), "", tiles.length, mySet); return mySet.size; }; var search = function (arr, ans, len, mySet) { if (len < 0) return; for (let i = 0; i < arr.length; i++) { if (!arr[i]) continue; let his = arr[i]; arr[i] = 0; mySet.add(ans + his); search(arr, ans + his, len - 1,mySet); arr[i] = his; } }