目录
1、编号3 Longest Substring Without Repeating Characters
2、编号6 ZigZag Conversion
3、编号20 Valid Parentheses
4、编号28 Implement strStr()
5、编号31 Longest Valid Parentheses
6、编号42 Multiply Strings
7、编号57 Length of Last Word
8、编号71 Simplify Path
9、编号72 Edit Distance
10、编号76 Minimum Window Substring
11、编号91 Decode Ways
12、编号98 Interleaving String
13、编号116 Distinct Subsequences
14、编号127 Word Ladder
15、编号128 Word Ladder II
16、编号140 Word Break
17、编号141 Word Break II
1、编号3 Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length
of 1.
一开始用二重循环O(n)的双指针解法。使用了长度为256的辅助数组记录是否碰到相同的字母。如果没找到相同字母，快指针向后走。如果找到了，慢指针走两步，快指针走一步。
class Solution {
public:
//For example, if the string is “abcdcedf”, what happens when you reach the second appearance of ‘c’?
int lengthOfLongestSubstring(string s) {
int i = 0, j = 0;
int result = 0;
bool exist[256] = { false };
while(j < s.length()) {
if(exist[s[j]]){
result = max(result, j - i);
while(s[i] != s[j]){
exist[s[i]] = false;
i++;
}
i++;
j++;
}else{
exist[s[j]] = true;
j++;
}
}
result = max(result, (int)s.length() - i);
return result;
}
};
2、编号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:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
这题很无语了，找数学公式，把字符分为红色和绿色两类。indexRed = (n-1)*2*j+i, indexGreen = indexRed+2*(n-i-1)
class Solution {
public:
string convert(string s, int nRows){
/*Initialization*/
if(nRows <= 1) return s;
string result;
if(s.size() ==0) return result;
for(int i =0; i< nRows; i++)
for(int j =0, indexRed = i; indexRed < s.size(); j++, indexRed = (nRows-1)*2*j+i){
/*Red Principal*/
result.append(1, s[indexRed]);
/*Green*/
if(i ==0 || i == nRows-1) continue;
int indexGreen = indexRed + 2*(nRows - i - 1); /*Times 2 to go a v shape to get green index*/
if(indexGreen < s.size()) result.append(1, s[indexGreen]);
}
return result;
}
};
3、编号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.
括号问题都不难解决，注意左括号和右括号分别处理。
class Solution {
public:
bool isValid(string s) {
stack<char> sk;
for(int i = 0; i < s.length(); i++){
if(s[i] == '(' || s[i] == '[' || s[i] == '{') sk.push(s[i]);
else{
if(sk.empty()) return false;
if(s[i] == ')' && sk.top() != '(') return false;
else if(s[i] == ']' && sk.top() != '[') return false;
else if(s[i] == '}' && sk.top() != '{') return false;
sk.pop();
}
}
if(sk.empty()) return true;
else return false;
}
};
4、编号28 Implement strStr()
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
haystack是目标字符串，needle是匹配字符串。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
if((*needle) == '\0') return haystack;
char *hayLoop = haystack;
int needleLength = strlen(needle);
int index = 0;
int inc = 1;
while(*(hayLoop + needleLength - 1) != '\0'){
if(hayLoop[index] == needle[index]){
index++;
/*Add this only to improve perfomance*/
/*Refer KMP algorithm*/
if(hayLoop[index] == needle[0] && inc==1)
inc = index - 1;
}else{
hayLoop += (inc==0?1:inc);
index = 0;
inc = 1;
}
if(index == needleLength) return hayLoop;
}
return NULL;
}
};
5、编号31 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.
线性时间的话要用dp来做。
class Solution {
public:
int longestValidParentheses(string s) {
/*DP result O(N)*/
/*初始dp[i]==i*/
/*使用dp[i]==j，表示i到某个j结点能够匹配*/
/*Initial*/
int result = 0;
int dp[s.size()];
for(int i = 0; i < s.size(); i++) dp[i] = i;
/*Fill dp*/
for(int i = 1; i < s.size(); i++) {
if(s[i] == '(') continue; //i is the next element. if next is '(' continue)
int x = i - 1; //x is set to connect all nodes one element back
if(dp[x] != x) x = dp[x] - 1; //if node x can not connect to node x, x is set back again
if(s[x] == '(') { //if current is '(')
dp[i] = x;
x--;
if(dp[x] != x) x = dp[x] - 1;
if(dp[i] != x + 1) dp[i] = x + 1;
}
if(i != dp[i] && ((i - dp[i] + 1) > result)) result = i - dp[i] + 1;
}
return result;
}
6、编号42 Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
字符串和数字转化问题。注意reverse的运用
class Solution {
public:
string multiply(string num1, string num2) {
if(num1.size() ==0 || num2.size() ==0) return 0;
string result(num1.size()+num2.size()+1, '0');
std::reverse(num1.begin(), num1.end());
std::reverse(num2.begin(), num2.end());
for(int i =0; i < num1.size(); i++) {
int dig1 = num1[i] -'0';
int carry = 0;
for(int j = 0; j< num2.size(); j++) {
int dig2 = num2[j] - '0';
int exist = result[i+j] -'0';
result[i+j] = (dig1*dig2+carry+ exist) % 10 +'0';
carry = (dig1*dig2+carry+exist)/10;
}
if(carry >0) result[i+num2.size()] = carry + '0';
}
std::reverse(result.begin(), result.end());
int start = 0;
while(result[start] =='0' && start < result.size()) start++;
if(start == result.size()) return "0";
return result.substr(start, result.size()-start);
}
};
7、编号57 Length of Last Word
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example, Given s = "Hello World", return 5.
注意最后一个字符有可能是空格。
class Solution {
public:
int lengthOfLastWord(const char *s) {
if(*s == NULL) return 0;
const char* p;
p = s;
bool inWord = false;
int length = 0;
while(*p != '\0'){
if(*p != ' ') {
if(!inWord) length = 0;
inWord = true;
length++;
}else inWord = false;
p++;
}
return length;
}
};
8、编号71 Simplify Path
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
click to show corner cases.
Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
一开始没看明白题。后来看了网上答案用栈来实现。
1. 等于“/”，跳过，直接开始寻找下一个element
2. 等于“.”，什么都不需要干，直接开始寻找下一个element
3. 等于“..”，弹出栈顶元素，寻找下一个element
4. 等于其他，插入当前elemnt为新的栈顶，寻找下一个element
最后，再根据栈的内容，重新拼path。这样可以避免处理连续多个“/”的问题。
class Solution {
public:
string simplifyPath(string path) {
vector<string> stack;
assert(path[0]=='/');
int i=0;
while(i< path.size())
{
while(path[i] =='/' && i< path.size()) i++; //skip the begining '////'
if(i == path.size())
break;
int start = i;
while(path[i]!='/' && i< path.size()) i++; //decide the end boundary
int end = i-1;
string element = path.substr(start, end-start+1);
if(element == "..")
{
if(stack.size() >0)
stack.pop_back();
}
else if(element!=".")
stack.push_back(element);
}
if(stack.size() ==0) return "/";
string simpPath;
for(int i =0; i<stack.size(); i++)
simpPath += "/" + stack[i];
return simpPath;
}
};
9、编号72 Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
应该是属于比较经典的DP题了。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.length()+1;/*! Use more dimension than the input!*/
int n = word2.length()+1;/*!*/
vector<vector<int>> dp;
for(int i = 0;i < m; i++){
vector<int> tmp;
for(int j = 0; j < n; j++) tmp.push_back(0);
dp.push_back(tmp);
}
for(int i = 0;i < m; i++) dp[i][0] = i;
for(int j = 0;j < n; j++) dp[0][j] = j;
for(int i = 1;i < m; i++)
for(int j = 1; j < n; j++)
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + ((word1[i-1] == word2[j-1]) ? 0 : 1));
return dp[m-1][n-1];
}
int min(int x, int y, int z){
int tmp = min(x,y);
return min(tmp, z);
}
int min(int x, int y){
if(x < y) return x;
else return y;
}
};
10、编号76 Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note: If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
这题用双指针解。快指针指到包含所有T中字符的时候，慢指针开始走，并保证慢指针走的时候仍然包含T中所有的字符。当慢指针走到不满足时，输出这时候的长度+1。然后快指针又开始走。这样循环到结尾就可以了。
class Solution {
public:
string minWindow(string S, string T) {
if(T.length() == 0|| S.length() == 0) return "";
vector<int> count1;
vector<int> count2;
/*Use count1 as counter, use count2 to recover count1*/
for(int i = 0; i < 256; i++){
count1.push_back(0);
count2.push_back(0);
}
for(int i = 0; i < T.length(); i++){
count1[T[i]]++;
count2[T[i]]++;
}
/*If count is zero, find a solution*/
int count = T.length();
int start = 0;
int minSize = INT_MAX;
int minStart;
for(int end = 0; end < S.length(); end++){
count1[S[end]]--;
if(count1[S[end]] >= 0) count--;
/*Use every char as start, handle end situation*/
if(count == 0){
while(true){
if(count2[S[start]] > 0){
if(count1[S[start]] < 0) count1[S[start]]++;
else break;
}
start++;
}
if(minSize > (end - start + 1)){
minSize = end - start + 1;
minStart = start;
}
}
}
if(minSize == INT_MAX) return "";
string result(S, minStart, minSize);
return result;
}
};
11、编号91 Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
一开始以为是比较容易的一维dp。当读入一个数字时，要么它自己是一个code，要么它跟前一位数字组成一个code。如果是前者，就取一个值，如果是后者，就把两种情况的值加起来。但是做了以后发现0特别难处理。因为0没有对应的字符，所以只能跟前面一个字符组合，这样就彻底乱了。最后采用了从后往前dp的特殊方法。
class Solution {
public:
int numDecodings(string s) {
if(s.length() == 0) return 0;
vector<int> dp(s.length()+2, 1);
for(int i = s.length()-1; i >= 0; i-- ){
if(s[i] == '0') dp[i] = 0;
else dp[i] = dp[i+1];
if(i+1 < s.length() && (s[i] == '1' || (s[i] == '2' && s[i+1] <= '6')))
dp[i] += dp[i+2];
}
return dp[0];
}
bool CheckValid(char num){
if(num == '0') return false;
return true;
}
bool CheckValid(char num1, char num2){
if(num1 == '1' || (num1 == '2' && num2 >= '0' && num2 <= '6'))
return true;
return false;
}
};
12、编号98 Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
用二维dp来做。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.length();
int n = s2.length();
if((m+n) != s3.length()) return false;
bool **dp = new bool*[m+1];/*use m+1 and n+1 to denotes empty string*/
for(int i = 0 ; i < m+1; i++) {
dp[i] = new bool[n+1];
for(int j = 0; j < n+1; j++)
dp[i][j] = false;//!!!!!!!!! Initial!!!!!!!!
}
dp[0][0] = true;
for(int i = 1; i < m+1; i++){
if(s1[i-1] == s3[i-1]) dp[i][0] = dp[i-1][0];
else dp[i][0] = false;
}
for(int j = 1; j < n+1; j++){
if(s2[j-1] == s3[j-1]) dp[0][j] = dp[0][j-1];
else dp[0][j] = false;
}
for(int i = 1; i < m+1; i++){
for(int j = 1; j < n+1; j++){
char x = s1[i-1];//!!!!!
char y = s2[j-1];
char z = s3[i+j-1];
if(x == z) dp[i][j] = dp[i-1][j] || dp[i][j];
if(y == z) dp[i][j] = dp[i][j-1] || dp[i][j];//z//
}
}
bool result = dp[m][n];
for(int i = 0; i < m; i++) delete dp[i];
delete dp;
return result;
}
};
13、编号116 Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is
not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
还是二维dp来做。列出例子如下。
/*
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
*/
class Solution {
public:
/*2D DP read*/
int numDistinct(string S, string T) {
int** dp;
dp = new int*[T.length() + 1];
for(int i = 0; i < T.length()+1; i++)
dp[i] = new int[S.length() + 1];
dp[0][0] = 1;
for (int i = 1; i <= T.length(); i++) dp[i][0] = 0;
for (int j = 1; j <= S.length(); j++) dp[0][j] = 1;
for (int i = 1; i <= T.length(); i++) {
for (int j = 1; j <= S.length(); j++) {
/*core*/
dp[i][j] = dp[i][j - 1];
if (T[i - 1] == S[j - 1]) dp[i][j] += dp[i - 1][j - 1];
}
}
return dp[T.length()][S.length()];
}
};
14、编号127 Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
word ladder是一类比较难的题目。用DFS来做。每一步从单词里面拆掉一个字母替换，然后看看改变字母后的单词在不在词典里。
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
if(start == end) return 0;
queue<string> q;
q.push(start);
queue<int> q_level;
q_level.push(1);
while(!q.empty()){
string s = q.front();
q.pop();
int currentLevel = q_level.front() + 1;
q_level.pop();
string tmp = s;
for(int i = 0; i < s.length(); i++){
for(int c = 'a'; c <= 'z'; c++){
if(s[i] == c) continue;
tmp[i] = c;
if(tmp == end) return currentLevel;
if(dict.count(tmp) > 0){ //important
q.push(tmp);
q_level.push(currentLevel);
dict.erase(tmp); //important
}
tmp[i] = s[i];//recover
}
}
}
return 0;
}
};
15、编号128 Word Ladder II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
只是额外输出结果而已。会做上题的话，这题就很简单。
class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
vector<vector<string>> result;
vector<string> r;
r.push_back(start);
if(start == end) {
r.push_back(end);
result.push_back(r);
return result;
}
queue<string> q;
q.push(start);
//queue<int> q_level;
//q_level.push(1);
while(!q.empty()){
string s = q.front();
q.pop();
//int currentLevel = q_level.front() + 1;
//q_level.pop();
string tmp = s;
for(int i = 0; i < s.length(); i++){
for(int c = 'a'; c <= 'z'; c++){
if(s[i] == c) continue;
tmp[i] = c;
if(tmp == end) {
r.push_back(end);
if(result.size() != 0 && r.size() > result[result.size()-1].size()) return result;
result.push_back(r);
r.clear();
r.push_back(start);
//return currentLevel;
}
if(dict.count(tmp) > 0){ //important
q.push(tmp);
//q_level.push(currentLevel);
dict.erase(tmp); //important
}
tmp[i] = s[i];//recover
}
}
}
return result;
}
};
16、编号140 Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
这一题用dp来做。
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
if(s.length() < 1) return true;
if(dict.empty()) return false;
unordered_set<string>::iterator it = dict.begin();
int maxlen=(*it).length(), minlen=(*it).length();
for(it++; it != dict.end(); it++)
if((*it).length() > maxlen) maxlen = (*it).length();
else if((*it).length() < minlen) minlen = (*it).length();
set<string> unmatched;
return wordBreakHelper(s,dict,unmatched,minlen,maxlen);
}
bool wordBreakHelper(string s,unordered_set<string> &dict,set<string> &unmatched,int mn,int mx) {
if(s.size() < 1) return true;
int i = mx < s.length() ? mx : s.length();
for(; i >= mn ; i--) {
string preffixstr = s.substr(0,i);
if(dict.find(preffixstr) != dict.end()){
string suffixstr = s.substr(i);
if(unmatched.find(suffixstr) != unmatched.end())
continue;
else
if(wordBreakHelper(suffixstr, dict, unmatched,mn,mx))
return true;
else
unmatched.insert(suffixstr);
}
}
return false;
}
};
17、编号141 Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
这两题都是比较难的。
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<vector<int>> prevs(s.length()+1);
vector<bool> checked(s.length()+1, false);
checked[0] = true;
for (int i = 1; i <= s.length(); ++i) {
for (int j = 0; j < i; ++j) {
if (checked[j] && dict.find(s.substr(j,i-j)) != dict.end()) {
if (!checked[i]) {
checked[i] = true;
}
prevs[i].push_back(j);
}
}
}
vector<string> res;
backtracking(s, prevs, res, s.length());
return res;
}
void backtracking(const string &s, const vector<vector<int>> &prevs, vector<string> &res, int index) {
for (int i = 0; i < prevs[index].size(); ++i) {
if (prevs[index][i] == 0) {
res.push_back(s.substr(0, index));
} else {
backtracking(s, prevs, res, prevs[index][i]);
for (int j = 0; j < res.size(); ++j) {
string temp = res[j];
temp.erase(remove( temp.begin(), temp.end(), ' '), temp.end());
if(temp.length() == prevs[index][i]){
res[j] += " " + s.substr(prevs[index][i], index-prevs[index][i]);
}
}
}
}
}
};
参考文献：
http://oj.leetcode.com/problems/