【每日一题/DFS/全排列/哈希表/计数】1079. 活字印刷 |
您所在的位置：网站首页 › 活字印刷字模 › 【每日一题/DFS/全排列/哈希表/计数】1079. 活字印刷 |
【每日一题/DFS/全排列/哈希表/计数】1079. 活字印刷
|
⭐️前面的话⭐️ 本篇文章介绍【1079. 活字印刷】题解，算法标签：【DFS】， 【哈希表】， 【计数】，展示语言c++/java。 📒博客主页：未见花闻的博客主页 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 📌本文由未见花闻原创，CSDN首发！ 📆首发时间：🌴2023年5月19日🌴 ✉️坚持和努力一定能换来诗与远方！ 💭推荐书籍：📚《算法》，📚《算法导论》 💬参考在线编程网站：🌐牛客网🌐力扣 博主的码云gitee，平常博主写的程序代码都在里面。 博主的github，平常博主写的程序代码都在里面。 🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！ 📌导航小助手📌 ⭐️1079. 活字印刷⭐️🔐题目详情💡解题思路🔑源代码 🌱总结
1079. 活字印刷 难度中等 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。 注意： 本题中，每个活字字模只能使用一次。 示例 1： 输入："AAB" 输出：8 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。示例 2： 输入："AAABBC" 输出：188示例 3： 输入："V" 输出：1提示： 1 if (u > n) return; set.insert(path); for (int i = 0; i s = tiles; n = s.size(); memset(st, 0, sizeof(st)); dfs(0, ""); return set.size() - 1; } };java代码： class Solution { Set set = new HashSet(); String s; boolean[] st; private void dfs(int u, StringBuilder ss) { if (u > s.length()) return; set.add(ss.toString()); for (int i = 0; i s = tiles; st = new boolean[s.length()]; dfs(0, new StringBuilder()); return set.size() - 1; } }思路2：哈希表计数+DFS搜索 c++代码： class Solution { public: int cnt[26]; int n; int ans; void dfs(int u) { if (u == n) return; for (int i = 0; i cnt[i]--; ans++; dfs(u + 1); cnt[i]++; } } } int numTilePossibilities(string tiles) { n = tiles.size(); memset(cnt, 0, sizeof(cnt)); //哈希计数 for (int i = 0; i if (u == n) return; for (int i = 0; i cnt[i]--; ans++; dfs(u + 1); cnt[i]++; } } } public int numTilePossibilities(String tiles) { n = tiles.length(); char[] cs = tiles.toCharArray(); //计数 Arrays.fill(cnt, 0); for (int i = 0; i |
【本文地址】