题解：学而思编程 字符串

【题目来源】学而思编程字符串【题目描述】小猴最近学习了字符串为了加强对字符串的理解猴博士特意给小猴安排了一道编程题给定一个字符串s ss保证s ss中只包含大写字母‘A’ - ‘Z’)请你判断字符串s ss中是否包含了全部26 2626个英文字母无论某个英文字母是以大写还是小写形式出现在字符串中均视为该字符串包含此字母。现在请你帮助小猴完成这个编程题。【输入】一行一个字符串s ss。【输出】一行如果给定字符串包含了全部26 2626个英文字母则输出Yes否则输出No。【输入样例】toosmallword【输出样例】No【核心思想】问题分析给定一个字符串s ss判断其是否包含全部26 2626个英文字母不区分大小写。这是一个**桶计数Bucket Counting**问题核心在于高效统计字符出现情况忽略大小写差异。算法选择统一大小写将所有字符转换为同一种大小写形式消除大小写差异桶数组Bucket Array利用布尔数组f ff标记每个字符是否出现实现O ( 1 ) O(1)O(1)的字符存在性查询关键步骤初始化创建布尔数组f [ 0..129 ] f[0..129]f[0..129]初始值为f a l s e falsefalse遍历字符串处理每个字符s i s_isi​若s i ∈ [ ′ A ′ , ′ Z ′ ] s_i \in [A, Z]si​∈[′A′,′Z′]s i ← s i − ′ A ′ ′ a ′ s_i \leftarrow s_i - A asi​←si​−′A′′a′转换为大写转小写标记出现f [ s i ] ← t r u e f[s_i] \leftarrow truef[si​]←true检查完整性遍历i ii从′ a ′ a′a′到′ z ′ z′z′若存在f [ i ] f a l s e f[i] falsef[i]false输出No并结束输出结果若26 2626个字母均出现输出Yes时间/空间复杂度时间复杂度O ( ∣ s ∣ 26 ) O(|s| 26)O(∣s∣26)遍历字符串O ( ∣ s ∣ ) O(|s|)O(∣s∣)检查26 2626个字母O ( 26 ) O(26)O(26)空间复杂度O ( 128 ) O(128)O(128)固定大小的 ASCII 码桶数组桶计数的核心思想哈希思想的简化实现利用字符的 ASCII 码值作为数组下标将字符映射到固定位置实现O ( 1 ) O(1)O(1)的标记和查询大小写归一化通过统一转换为小写或大写将52 5252个可能字符压缩为26 2626个有效状态简化统计逻辑布尔标记替代计数只需知道字符是否出现无需统计出现次数使用b o o l boolbool类型即可满足需求空间更优提前终止优化一旦发现某个字母缺失立即输出结果避免不必要的完整遍历适用于字符集有限、需要快速判断元素存在性的统计类问题【解题思路】【算法标签】#字符串入门【代码详解】#includebits/stdc.husingnamespacestd;boolf[130];// 直接按照ASCII码定义数组intmain(){string s;cins;// 统一成小写统计每个字母是否出现for(inti0;is.size();i){if(s[i]As[i]Z){s[i]s[i]-Aa;}f[s[i]]true;// 使用桶记录每个字符}for(intia;iz;i){// 遍历26个字母的下标if(!f[i]){// 如果其中有f[i]falsecoutNoendl;// 输出Noreturn0;}}coutYesendl;// 如果可以遍历完则输出Yesreturn0;}【运行结果】toosmallword No