# String

## 49. Group Anagrams 群组错位词

Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. 解法1 vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, vector<string>> m; for (string str : strs) { string t = str; sort(t.begin(), t.end()); // 这里可以不用判断m[t]存不存在 m[t].push_back(str); } for (auto a : m) { res.

## 43. Multiply Strings 字符串相乘

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

## 38. Count and Say 计数和读法

The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth term of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string.

## 32. Longest Valid Parentheses 最长有效括号

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4. Difficulty: Hard 这道题比20. Valid Parentheses 验证括号难一些. 解法1 还是利用栈来求解,并定义start记录合法括号串的起始位置.遍历字符串,如果遇到左括号,则将当前下标压栈,如果遇到右括号,如果当前栈为空,则将下一个位置的下标记为start,如果栈不为空,则将栈顶元素取出.此时如果站为空,则更新结果和i-start+1的最大值,否则更新结果为i-栈顶元素的最大值. class Solution { public: int longestValidParentheses(string s) { int res = 0,start = 0; stack<int> m; for (int i=0;i<s.

## 30. Substring With Concatenation of All Words 串联所有单词的子串

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. For example, given: s: "barfoothefoobarman" words: ["foo", "bar"] You should return the indices: [0,9]. (order does not matter). Difficulty: Hard 这道题让我们求串联所有单词的子串.所有单词来自输入的数组.所有单词的长度一样,串联的顺序不一定.如题中的例子,可以串联成foobar, barfoo. 这里我们用两个哈希表,一个用来存输入单词数组的每个单词和其的出现次数.然后遍历输入的字符串.设单词的个数为n,每个单词长度为m.每次遍历检查母字符串从该位置开始,每m截取一下查看在第一个哈希表是否存在.如果存在,存入第二个哈希表.如果n个次截取都匹配则这次遍历是符合要求的,存一下结果. 解法1 就是上面分析 class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int>res; if (s.

## 28. Implement strStr() 实现strStr()函数

Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1 Difficulty: Easy 这道题让我们找出字符串中某个子字符串第一次出现的index.如果子字符串的长度为0,则返回0,如果子字符传的长度大于母字符串,则返回-1.遍历字符串的时候只需要遍历到剩下的长度等于字符串的位置即可. class Solution { public: int strStr(string haystack, string needle) { if (needle.empty()) return 0; int m = haystack.size(),n=needle.size(); if (m<n) return -1; for (int i=0;i<=m-n;++i) { int j=0; for (j=0;j<n;j++) if (haystack[i+j]!

## 22. Generate Parentheses 生成括号

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Difficulty: Medium 这道题让我们列举出所有的括号字符串,前面还有一题20. Valid Parentheses 验证括号也是关于括号的.这里让列举出所有可能,可以优先考虑递归和DFS.定义left,right分别表示剩余左括号的数量和剩余的右括号的数量.如果在某次的递归中,left>right说明在已经生成的字符串中右括号的数量大于左括号的数量,是不合理的.当left,right都为0的时候,说明已经生成一个可用的括号串.其实这里有DFS的思想.为什么呢.看看下面是怎样递归的顺序,以题目给的例子n=3. ( (( ((( ((() ((()) ((())) (()()) ~ ()()() DFS(深度优先),这里可以想象成左括号优先 解法1 就是上面分析的解法 class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; generateParenthesisDFS(n,n,"",res); return res; } void generateParenthesisDFS(int left,int right,string out,vector<string>& res) { if (left>right) return; if (left==0 && right==0) res.

## 20. Valid Parentheses 验证括号

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. Difficulty: Easy 这道题让我们验证字符串是否是可用的括号,这个字符串只有括号.需要用到栈,当遇到左括号的时候压入到栈里,遇到右括号的时候需要检查栈顶元素是否为对应的左括号,如果不是对应的就返回false. class Solution { public: bool isValid(string s) { stack<char> parentheses; for (int i = 0; i<s.size();i++){ if (s[i]=='('||s[i]=='['||s[i]=='{') parentheses.push(s[i]); else { if (parentheses.empty()) return false; if (s[i]==')' && parentheses.

## 17. Letter Combinations of a Phone Number 电话号码的字母组合

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 这道题让我们求电话号码的字母组合, 既2~9中,每个数字都代表2到3个字母,然后给出一个数字的字符串,求出这串数字可能代表的所有字母串.这道题可以用DFS的思想解决,关于DFS可以看二叉树 深度优先搜索（DFS）、广度优先搜索（BFS）,可以简单的了解一下.那为什么说是DFS思想呢,比如给出”2345”,那个对应的结果为adgj,adgk,adgl,adhj,adhk,adhl...cfil这个顺序可以看做DFS的思想.大概这个意思. 解法1 解法1就是上面的分析的解法. class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.

## 14. Longest Common Prefix 最长共同前缀

Write a function to find the longest common prefix string amongst an array of strings. Difficulty: Easy 可以把输入的字符串数组,看成一个char的二维数组,定义指针i,j分别代表行数和列数,逐列查找,如果char[i][j]不等于char[0][j]或者第i个字符串的长度小于j就可以返回之前的结果了. class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; string res = ""; for (int j=0;j<strs[0].size();j++) { char c = strs[0][j]; for (int i=1;i<strs.size();i++) { if (j>=strs[i].size() || strs[i][j]!=c) return res; } res += c; } return res; } };

## 13. Roman to Integer 罗马数字转化成整数

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. Difficulty: Easy 这道题是把罗马数字转化成整数,和12. Integer to Roman 整数转罗马数字正好反着.关于罗马数字的简单介绍可以回看12. Integer to Roman 整数转罗马数字. 这道题明确告诉我们输入的是罗马数字,所有不需要验证是否为罗马数字.下面只需要考虑 如果当前数字是最后一个数字,或之后的数字比它小的话,则加上当前的数字.举个反例CD-400,D比C大,所以先减去C(100)再加上D(500),就得到结果400 其他情况则减去这个数字 #include <unordered_map> using namespace std; class Solution { public: int romanToInt(string s) { int res = 0; unordered_map<char, int> m{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; for (int i = 0; i < s.size(); i++) { int val = m[s[i]]; //m[s[i+1]]不需要考虑越界,因为有'\0' m['\0']=0 if (i == s.

## 12. Integer to Roman 整数转罗马数字

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. Difficulty: Medium 罗马字符: I V X L C D M 阿拉伯数字: 1 5 10 50 100 500 1000 1~9 : I, II, III, IV, V, VI, VII, VIII, IX 10~90 : X, XX, XXX, XL, L, LX, LXX, LXXX, XC 100~900: C, CC, CCC, CD, D, DC, DCC, DCCC, CM 1000~3000: M, MM, MMM 例如: 整数1437的罗马数字为MCDXXXVII.

## 10. Regular Expression Matching 正则表达式匹配

Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true Difficulty: Hard

## 8 String to Integer Atoi 把字符串转换成整数

Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases. Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front. Difficulty: Medium 把字符串转换成整数,和剑指offer 49题相似,不过这里的要求比较多,实现atoi 判断开头是否有空格 判断开头是否有 '+','-' 如果遇到非法字符返回已有的结果 如果超过边界,返回边界值 class Solution { public: int myAtoi(string str) { int len = str.

## 6 ZigZag Conversion 之子形转换字符串

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows:

## Longest Palindromic Substring 最长回文子字符串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Difficulty:Medium Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example: Input: "cbbd" Output: "bb" 这道题参考Grandyang,他博客里有全套leetcode讲解. 求最长回文串,回文串就是正着读反着读都一样的字符串.下面的解法是以一个字符为中心向两边扩散并比较 解法1: O(n^2) class Solution { public: public: string longestPalindrome(string s) { int startIdx = 0, left = 0, right = 0, len = 0; for (int i = 0; i < s.

## Longest Substring Without Repeating Characters 子字符串的最大不重复长度

Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. 滑动窗口问题,比如abcabcbb,滑动到abca的时候需要丢弃第一个a变成bca,继续向右滑动,每次滑动都要检查有没有重复.感觉涉及到最大,最多的问题都可以试着网哈希表上靠. class Solution { public: int lengthOfLongestSubstring(string s) { int size = s.