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
.
Example 1:
Input: tiles = "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:
Input: tiles = "AAABBC" Output: 188
Example 3:
Input: tiles = "V" Output: 1
Constraints:
1 <= tiles.length <= 7
tiles
consists of uppercase English letters.
活字印刷。
你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意:本题中,每个活字字模只能使用一次。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/letter-tile-possibilities
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是 DFS backtracking。这道题有点类似求子集那一类的题。因为 input 中有可能有重复字母,为了不重复使用,我们需要将 input 字符串中的字母进行排序,再通过一个额外的 visited 数组判断某个字母是否有被重复使用。
时间O(nlogn)
空间O(n)
Java实现
1 class Solution { 2 int count; 3 4 public int numTilePossibilities(String tiles) { 5 count = 0; 6 char[] letters = tiles.toCharArray(); 7 Arrays.sort(letters); 8 boolean[] visited = new boolean[letters.length]; 9 dfs(letters, 0, visited); 10 return count; 11 } 12 13 private void dfs(char[] letters, int index, boolean[] visited) { 14 if (index == letters.length) { 15 return; 16 } 17 for (int i = 0; i < letters.length; i++) { 18 if (visited[i]) { 19 continue; 20 } 21 if (i - 1 >= 0 && letters[i] == letters[i - 1] && !visited[i - 1]) { 22 continue; 23 } 24 count++; 25 visited[i] = true; 26 dfs(letters, index + 1, visited); 27 visited[i] = false; 28 } 29 } 30 }
标签:count,tiles,letters,int,Possibilities,Tile,visited,LeetCode From: https://www.cnblogs.com/cnoodle/p/17415086.html