【LeetCode系列】【字符串专题】

mac2026-08-12 5

专题四：字符串专题

LeetCode 38 报数

题目：https://leetcode-cn.com/problems/count-and-say/submissions/

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"）, 即 21。 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1 输出: "1"

示例 2:

输入: 4 输出: "1211"

1、分析

这题有点儿难读懂，其实就是比如：1211，读作：一个1，一个2，两个1，所以下一次输出就是：111221；一个1即是11，一个2即是12，两个1即是21。所以我们针对上一个的输出，就需要计算当前数字的个数，这个很有套路，就是例如记录和下标i相同的元素有多少个：

for(int i=0;i<nums.size();i++) { int num=0,j=i; while(j<nums.size()&&nums[j]==nums[i]) num++; }

2、代码

class Solution { public: string countAndSay(int n) { string res="1"; for(int i=0;i<n-1;i++) { string temp; for(int j=0;j<res.size();j++) { int k=j; while(k<res.size()&&res[k]==res[j]) k++; //计算和当前数字相同的有多少个 temp+=to_string(k-j)+res[j]; j=k-1; } res=temp; } return res; } };

LeetCode 49 字母异位词分组

题目：https://leetcode-cn.com/problems/group-anagrams/

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]

说明：

所有输入均为小写字母。不考虑答案输出的顺序。

1、分析

对于这种分类问题，我们一定要找到分组的标准是什么，即一组的共同点是什么。我们可以发现每一组内的组成字符串的字符都是一样的，只是顺序不同，但如果我们对每个字符串排序一下，就会变成一样的。所以如果我们对排序后字符串一样的就可以归为一组，我们可以用一个哈希表来存储，哈希表的下标用分组的标识即排序后的字符串，哈希表的内容即是存储归为一组的结果集。

2、代码

class Solution { public: unordered_map<string,vector<string>> m; vector<vector<string>> ans; vector<vector<string>> groupAnagrams(vector<string>& strs) { if(strs.empty()) return ans; for(auto temp:strs) { string tt=temp; sort(tt.begin(),tt.end()); m[tt].push_back(temp); } for(auto temp:m) { ans.push_back(temp.second); } return ans; } };

LeetCode 151 翻转字符串里的单词

题目：https://leetcode-cn.com/problems/reverse-words-in-a-string/

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue" 输出: "blue is sky the"

示例 2：

输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

1、分析

先是反转每个单词，再整个反转即可实现最终效果。例如：

2、代码

class Solution { public: string reverseWords(string s) { int k=0; for(int i=0;i<s.size();i++) { while(i<s.size()&&s[i]==' ') i++; if(i==s.size()) break; int j=i; while(j<s.size()&&s[j]!=' ') j++; reverse(s.begin()+i,s.begin()+j); //反转每个单词 if(k) s[k++]=' '; while(i<j) s[k++]=s[i++]; } s.erase(s.begin()+k,s.end()); //除去后面的空格 reverse(s.begin(),s.end()); return s; } };

LeetCode 165 比较版本号

题目：https://leetcode-cn.com/problems/compare-version-numbers/submissions/

比较两个版本号 version1 和 version2。如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1，除此之外返回 0。

你可以假设版本字符串非空，并且只包含数字和 . 字符。

. 字符不代表小数点，而是用于分隔数字序列。

例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。

你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。

示例 1:

输入: version1 = "0.1", version2 = "1.1" 输出: -1

示例 2:

输入: version1 = "1.0.1", version2 = "1" 输出: 1

1、分析

即从第一个数开始比较，当第一个数比较大时，返回1，当第二个数比较大时，返回-1，若当前比较数相等则比较下一个数，当当前位置没有数时，即是0。例如：

2、代码

class Solution { public: int compareVersion(string version1, string version2) { for(int i=0,j=0;i<version1.size()||j<version2.size();i++,j++) { int k1=i; int num1=0; while(k1<version1.size()&&version1[k1]!='.') k1++; if(k1==i) num1=0; //若当前没有数，则为0 else //计算当前数值 { while(i<k1) num1=num1*10+version1[i++]-'0'; } int k2=j; int num2=0; while(k2<version2.size()&&version2[k2]!='.') k2++; if(k2==j) num2=0; //若当前没有数，则为0 else //计算当前数值 { while(j<k2) num2=num2*10+version2[j++]-'0'; } if(num1>num2) return 1; if(num1<num2) return -1; } return 0; } };

LeetCode 929 独特的电子邮件地址

题目：https://leetcode-cn.com/problems/unique-email-addresses/

每封电子邮件都由一个本地名称和一个域名组成，以 @ 符号分隔。

例如，在 alice@leetcode.com中， alice 是本地名称，而 leetcode.com 是域名。

除了小写字母，这些电子邮件还可能包含 '.' 或 '+'。

如果在电子邮件地址的本地名称部分中的某些字符之间添加句点（'.'），则发往那里的邮件将会转发到本地名称中没有点的同一地址。例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。（请注意，此规则不适用于域名。）

如果在本地名称中添加加号（'+'），则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件，例如 m.y+name@email.com 将转发到 my@email.com。（同样，此规则不适用于域名。）

可以同时使用这两个规则。

给定电子邮件列表 emails，我们会向列表中的每个地址发送一封电子邮件。实际收到邮件的不同地址有多少？

示例：

输入：["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] 输出：2 解释：实际收到邮件的是 "testemail@leetcode.com" 和 "testemail@lee.tcode.com"。

1、分析

对于统计新的邮件地址个数，可以用一个哈希表来存最后的结果，因为哈希表会自动处理掉重复的地址。

2、代码

class Solution { public: unordered_set<string> s; int numUniqueEmails(vector<string>& emails) { if(emails.empty()) return 0; for(auto temp:emails) { auto at=temp.find('@'); //找到本地地址 string now; for(auto c:temp.substr(0,at)) //跟新本地地址 { if(c=='+') break; if(c!='.') now+=c; } now+=temp.substr(at); //加上后面的域名 s.insert(now); //把新的邮件存入哈希表中 } return s.size(); //哈希表的大小即是最终的结果 } };

LeetCode 5 最长回文子串

题目：https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

1、分析

我们在这里枚举中点，然后分别用两个指针从中点出发，向左右开始遍历，当遍历到的字符相同时，则继续遍历，否则返回结果，即是以当前字符为中点的最长回文子串。

值得注意的是：当我们的子串长度为奇数时，中点是一个字符，但如果子串长度为偶数，则中点字符是两个字符。

2、代码

class Solution { public: string longestPalindrome(string s) { string res; for(int i=0;i<s.size();i++) { //子串长度为奇数 for(int j=i,k=i;j>=0&&k<s.size()&&s[j]==s[k];j--,k++) { if(res.size()<k-j+1) res=s.substr(j,k-j+1); } //子串长度为偶数 for(int j=i,k=i+1;j>=0&&k<s.size()&&s[j]==s[k];j--,k++) { if(res.size()<k-j+1) res=s.substr(j,k-j+1); } } return res; } };

LeetCode 6 Z字形变换

题目：https://leetcode-cn.com/problems/zigzag-conversion/submissions/

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L C I R E T O E S I I G E D H N 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"

1、分析

这一题的主要思路就是找规律，找到应该输出的下标和原来的下标有什么关系即可。

2、代码

class Solution { public: string convert(string s, int n) { if(n==1) return s; //后面有n-1，所以当n=1时，单独考虑 string res; for(int i=0;i<n;i++) { if(i==0||i==n-1) //第0行和最后一行单独考虑 { for(int j=i;j<s.size();j+=2*(n-1)) res+=s[j]; } else //中间行两个等差数列交错 { for(int j=i,k=2*(n-1)-i;j<s.size()||k<s.size();j+=2*(n-1),k+=2*(n-1)) { if(j<s.size()) res+=s[j]; if(k<s.size()) res+=s[k]; } } } return res; } };

LeetCode 3 无重复字符的最长子串

题目：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

1、分析

我们在这里枚举每个最长子串的终点。

即起点满足单调原则。这样时间复杂度为O(n)。对于怎样判断两个指针间的元素是否无重复元素，可以用一个哈希表来存储，当有字符的个数大于1时，则需要把红色指针往后移动。

2、代码

class Solution { public: int lengthOfLongestSubstring(string s) { int res=0; unordered_map<char,int> m; for(int i=0,j=0;i<s.size();i++) { m[s[i]]++; //若有重复元素，即一定是新加入的元素，所以只需要判断当前元素的个数是否大于1即可 while(m[s[i]]>1) m[s[j++]]--;//删掉j指的字符，并把j向后移动 res=max(res,i-j+1); } return res; } };

LeetCode 208 实现Trie(前缀树)

题目：https://leetcode-cn.com/problems/implement-trie-prefix-tree/

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。

1、分析

在这里，我们创建一个结构体，有一个bool变量用来标记一个单词是否存在，还有一个自身结构的数组变量。由于一共就26个字符，所以数组大小为26就够了。

2、代码

class Trie { public: struct Node { bool is_end; Node* son[26]; Node() { is_end=false; for(int i=0;i<26;i++) { son[i]=NULL; } } }*root; /** Initialize your data structure here. */ Trie() { root=new Node(); } /** Inserts a word into the trie. */ void insert(string word) { auto p=root; for(auto c:word) { int u=c-'a'; //判断当前字符是不是已存在 if(p->son[u]==NULL) p->son[u]=new Node(); p=p->son[u]; } p->is_end=true; } /** Returns if the word is in the trie. */ bool search(string word) { auto p=root; for(auto c:word) { int u=c-'a'; if(p->son[u]==NULL) return false; p=p->son[u]; } return p->is_end; //需要判断单词是不是存在 } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { auto p=root; for(auto c:prefix) { int u=c-'a'; if(p->son[u]==NULL) return false; p=p->son[u]; } return true; //前面都相等，即为前缀相等 } }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */

LeetCode 273 整数转换英文表示

题目：https://leetcode-cn.com/problems/integer-to-english-words/

将非负整数转换为其对应的英文表示。可以保证给定输入小于 231 - 1 。

示例 1:

输入: 123 输出: "One Hundred Twenty Three"

1、分析

2、代码

class Solution { public: string small[20]={"Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine", "Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen", "Seventeen","Eighteen","Nineteen"}; string decade[10]={"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"}; string big[4]={"Billion","Million","Thousand",""}; string numberToWords(int num) { if(!num) return small[0]; string res; for(int i=1000000000,j=0;i>0;i/=1000,j++) //开始枚举 { if(num>=i) { res+=get_part(num/i)+big[j]+' '; num%=i; } } while(res.back()==' ') res.pop_back(); //后面可能有多余的空格 return res; } string get_part(int num) { string res; if(num>=100) { res+=small[num/100]+" Hundred "; num%=100; } if(!num) return res; if(num>=20) { res+=decade[num/10]+' '; num%=10; } if(!num) return res; res+=small[num]+' '; return res; } };

最新回复(0)

【LeetCode系列】【字符串专题】

目录

专题四：字符串专题

LeetCode 38 报数

1、分析

2、代码

LeetCode 49 字母异位词分组

1、分析

2、代码

LeetCode 151 翻转字符串里的单词

1、分析

2、代码

LeetCode 165 比较版本号

1、分析

2、代码

LeetCode 929 独特的电子邮件地址

1、分析

2、代码

LeetCode 5 最长回文子串

1、分析

2、代码

LeetCode 6 Z字形变换

1、分析

2、代码

LeetCode 3 无重复字符的最长子串

1、分析

2、代码

LeetCode 208 实现Trie(前缀树)

1、分析

2、代码

LeetCode 273 整数转换英文表示

1、分析

2、代码