Leetcode刷题java之1079. 活字印刷

淩亂°似流年 2023-07-03 02:59 1阅读 0赞

可参考本博客回溯法专栏的最后一条的回溯法框架

[https://blog.csdn.net/qq\_41901915/article/details/104113330][https_blog.csdn.net_qq_41901915_article_details_104113330]

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了100.00% 的用户

内存消耗 :34.1 MB, 在所有 Java 提交中击败了72.33%的用户

题目：

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

示例 1：

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

示例 2：

输入："AAABBC"  
输出：188

提示：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/letter-tile-possibilities  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

采用回溯法，利用框架就可以了，关键在于如何去重

代码：

class Solution {
        int result=0;
        public int numTilePossibilities(String tiles) {
            char[] ch=tiles.toCharArray();
            Arrays.sort(ch);
            boolean[] visit=new boolean[ch.length];
            backtrack(visit,ch);
            return result;
        }
        public void backtrack(boolean[] visit,char[] ch)
        {
            for(int i=0;i<ch.length;i++)
            {
                //这是这个代码核心的部分
                //选过一次的一定不会再选了
                //如果与前面一个字母相同，且它已经回退过了，说明它已经选完了
                if(visit[i]||(i>0&&ch[i]==ch[i-1]&&!visit[i-1]))
                {
                    continue;
                }
                result++;
                visit[i]=true;
                backtrack(visit,ch);
                visit[i]=false;
            }
        }
    }

[https_blog.csdn.net_qq_41901915_article_details_104113330]: https://blog.csdn.net/qq_41901915/article/details/104113330