← 返回目录

算法笔试模拟题精解之“Password”

第 46 / 74 卷日期：

算法笔试模拟题精解之“Password”

贡献者 | 陈苇彬

简介：可以用枚举法解决这个问题。

题目描述

题目等级：容易

知识点：字符串、枚举

查看题目：Password

Tom 在期末考完试以后学习了 Python 语言，他发现 Python 语言确实是简洁又

强大，在他学完字符串以后，他写了一个随机生成密码的 python 文件。

原理是这样的，输入一个字符串 s，然后系统会随机将这个 s 重新任意排序，然

后又生成两个字符串 s1 和 s2，并拼接起来最终生成随机密码 str = s1 + s + s2。

现在 Tom 有一个问题要问你，每次给你两个字符串，一个是 s( 表示输入的字符

串 )，一个是 str( 表示产生的随机字符串 )，问这两个字符串是否符合上述要求的原

理？如果符合输出 YES，否则输出 NO。1<=s,str<=100

输入两个字符串，一个是 s，表示输入的字符串，一个是 str，表示产生的随机

字符串（1<=s,str<=100）

输出内容为一行字符串，如果符合题意中的原理输出 "YES"，否则输出 "NO"。

示例 1

输入：

"abc"

"xxxcabyyy"

输出：

"YES"

解题方法：枚举法

解题过程中用到的参数列出：

char[] s1 : 密码字符串的字符数组格式

char[] str1 : 随机生成字符串的数组格式

int[] S : 密码字符串中每个字符出现的个数。(i : 0-25)

int[] temp : S 数组的备份，用于恢复 S（使用 clone 方法获得）

count : 表示成功匹配到的密码字符的个数

计算过程：

  1. 将提供的字符串转换为字符数组 s1 和 str1
  2. 用一个长度为 26 的 int 型数组对密码中各个字符出现的次数进行统计。
  3. 从第一个字符开始，对之后的挨个序列进行判断

（1）如果 s1 中有这个字符 , 则在 S 中将这个字符的个数减 1（减了之后判断该

字符个数是否小于 0），同时将 count+1

若减完后 S 中对应字符个数小于 0，则表示该序列与 s1 不匹配，则将 count

重置为 0, 并使用 temp 对 S 进行重置 , 然后直接跳到下一个字符进行判断。

的值 ( 即 count 的值 = s1 中字符的个数 )，则代表这个就是密码，可以直接输出

"YES" 了

（3）如果对整个 str1 遍历一遍后仍找不到与 s1 匹配的序列 , 则表示 str1 中没有

密码 , 则输出 "NO"

特殊情况：如果随机字符串 str 的长度小于密码字符串 s 的长度 , 则肯定无法匹

配成功 , 这个时候就直接返回 "NO"

时间复杂度 : O(n^2)

空间复杂度 : O(n)

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：Password

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”