X

LEETCODE 1079. Letter Tile Possibilities 解题思路分析

题目大意:

活字印刷

你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

示例 1:

输入:"AAB"
输出:8
解释:可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2:

输入:"AAABBC"
输出:188

提示:

  1. 1 <= tiles.length <= 7
  2. tiles 由大写英文字母组成

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1079

解题思路分析:

看题目提示 tiles 的数量级并不是太大,最大长度为7,这代表着暴力解是有可能通过的。通常情况下,求所有的排列组合可以想到使用dfs深度搜索来解决。我们将 tiles 中的每一个字符看作为一个节点,以任意一个字符为起点dfs每一条路径就可以搜索出所有的线路。不过本题需要注意存在重复答案,如何排重是本题优化的关键。

思路大致如下:

  1. 首先将 tiles 字符串中每种字符出现的次数统计出来。
  2. 以每种字符作为起点开始dfs查找。这样,相同的字符不会重复作为起点,从而避免了重复。

看下详细代码:

public int numTilePossibilities(String tiles) {
    int[] count = new int[26]; // 统计每种字符出现的次数
    for(int i=0;i<tiles.length();i++){
        count[tiles.charAt(i)-'A']++;
    }
    return dfs(count); // 开始dfs(递归)
}
int dfs(int[] count){
    int res=0; // 返回值,组合个数
    for(int i=0;i<26;i++){ // 以每一个大写字母作为起点循环
        if(count[i]==0){ // 该字母个数为0,跳过
            continue;
        }
        res++; // 返回结果加一。
        count[i]--; // 消耗当前字符
        res+=dfs(count); // 递归到下一层求子问题解(消耗掉当前字符后的解)。
        count[i]++; // 还原当前字符继续循环
    }
    return res;
}

本解法用时1ms。

Runtime: 1 ms, faster than 99.02% of Java online submissions for Letter Tile Possibilities.

Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.


解法二:

还有一种稍微效率低一点的解法,这是我一开始想到的,思路大体也是dfs,但排重操作使用的Set类,执行速度肯定比不上第一种,这里仅作参考。

Set<String> res = new HashSet<>();
public int numTilePossibilities(String tiles) {
    help(tiles, new boolean[tiles.length()],"");
    return res.size();
}

void help(String tiles, boolean[] visited, String s){
    for(int i=0;i<tiles.length();i++){
        if(!visited[i]){
            visited[i] = true;
            String temp = s + tiles.charAt(i);
            res.add(temp);
            help(tiles, visited, temp);
            visited[i] = false;
        }
    }
}

本解法用时29ms。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1079-letter-tile-possibilities-解题思路分析/
Categories: leetcode
kwantong: