String
1 Reverse Vowels of a String
https://leetcode.com/problems/reverse-vowels-of-a-string/
>
string reverseVowels(string s) {
string res=s;
set<char> vowels{'a','e','i','o','u','A','E','I','O','U'};
int i=0,j=s.size()-1;
while(i<j){
while(i<j&&vowels.count(s[i])==0) i++;
while(i<j&&vowels.count(s[j])==0) j--;
res[i]=s[j];
res[j]=s[i];
i++;
j--;
}
return res;
}
2 Reverse Vowels of a String
https://leetcode.com/problems/reverse-string/
>
string reverseString(string s) {
string res=s;
int i=0,j=s.size()-1;
while(i<j){
res[i]=s[j];
res[j]=s[i];
i++;
j--;
}
return res;
}
3 Longest Substring Without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Hash Table Method
>
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> index;
int maxLen=0;
int j=0;
for(int i=0;i<s.size();i++){
if(index.count(s[i])>0) j=max(j,index[s[i]]+1);
index[s[i]]=i;
maxLen=max(maxLen,i-j+1);
}
return maxLen;
}
4 Longest Substring with At Most Two Distinct Characters
>
lengthOfLongestSubstringTwoDistinct(string s){
unordered_map<char,int> index;
int maxLen=0,count=0;
int j=0;
for(int i=0;i<s.size();i++){
index[s[i]]++;
if(index[s[i]]==1) count++;
while(count>2){
index[s[j]]--;
if(index[s[j]]==0) count--;
j++;
}
maxLen=max(maxLen,i-j+1);
}
return maxLen;
}
5 Longest Substring with At Most K Distinct Characters
using hash table to keep a sliding window of size k
>
lengthOfLongestSubstringKDistinct(String s, int k)
unordered_map<char,int> index;
int maxLen=0,count=0;
int j=0;
for(int i=0;i<s.size();i++){
index[s[i]]++;
if(index[s[i]]==1) count++;
while(count>k){
index[s[j]]--;
if(index[s[j]]==0) count--;
j++;
}
maxLen=max(maxLen,i-j+1);
}
return maxLen;
}
>
string longestSubstringKDistinct(String s, int k)
if(s.size()==0||k==0) return "";
unordered_map<char,int> cnt;
int start=0,j=0,count=0,maxLen=0;
for(int i=0;i<s.size();i++){
if(++cnt[s[i]]==1) count++;
while(count>k){
if(--cnt[s[j++]]==0){
count--;
if(maxLen<i-j+1){
maxLen=i-j+1;
start=j;
}
}
}
}
return s.substr(start,maxLen);
}
string to stream, given a function streamreader.read() returns next character
>
string longestSubstringKDistinct(int k)
if(k==0) return "";
unordered_map<char,int> index;
set<pair<int,char> > st;
string s="";
char c;
int start=0,j=0,i=0,maxLen=0;
while(streamreader.read(c)){
s+=c;
while(cnt.size()==k&&cnt.count(c)==0){
char temp=*st.begin().second;
j=*st.begin().first;
cnt.erase(temp);
st.erase(st.begin());
if(i-j>maxLen){
maxLen=i-j;
start=j;
}
}
if(cnt.count(c)>0) st.erase(cnt[c]);
st.insert({i,c});
cnt[c]=i;
i++;
}
return s.substr(start,maxLen);
}
6 Palindrome Pairs
https://leetcode.com/problems/palindrome-pairs/
>
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int> > res;
unordered_map<string,int> index;
set<int> lens;
for(int i=0;i<words.size();i++){
index[words[i]]=i;
lens.insert(words[i].size());
}
for(int i=0;i<words.size();i++){
string s=words[i];
reverse(s.begin(),s.end());
if(index.count(s)&&index[s]!=i) res.push_back({i,index[s]});
auto ls=lens.find(s.size());
for(auto it=lens.begin();it!=ls;it++){
int len=*it;
if(isPalindrome(words[i].substr(0,s.size()-len))&&index.count(s.substr(0,len)))
res.push_back({index[s.substr(0,len)],i});
if(isPalindrome(words[i].substr(len))&&index.count(s.substr(s.size()-len)))
res.push_back(i,index[s.substr(s.size()-len)]);
}
}
return res;
}
bool isPalindrome(string s){
int i=0,j=s.size()-1;
while(i<j){
if(s[i++]!=s[j--]) return false;
}
return true;
}
7 Integer to English Words
https://leetcode.com/problems/integer-to-english-words/
>
class numberToWords{
public:
vector<string> thousands={"","Thousand","Millon","Billion"};
vector<string> tens={"","Ten","Twenty","Thirty","Forty",
"Fifty","Sixty","Seventy","Eighty","Ninety"};
vector<string> less_than_20={"","One","Two","Three","Four","Five","Six","Seven","Eight",
"Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen",
"Sixteen","Seventeen","Eighteen","Nineteen"};
string(int num){
string res;
if(num==0) return "Zero";
int i=0;
while(num>0){
if(num%1000>0){
res=helper(num%1000)+thousands[i]+" "+res;
}
num/=1000;
i++;
}
for(auto it=res.end()-1;it!=res.begin();it--){
if(*it==' ') res.erase(it);
}
return res;
}
string helper(int num){
string res="";
if(num==0) return res;
if(num<20){
res=less_than_20[num]+" ";
}else if(num<100){
res=tens[num/10]+" "+less_than_20[num%10];
}else{
res=less_than_20[num/100]+" Hundred "+helper(num%100);
}
return res;
}
};
8 Basic Calculator
https://leetcode.com/problems/basic-calculator/
Use a stack
>
int calculate(string s) {
int res=0;
int sign=1;
stack<int> st;
int num=0;
for(int i=0;i<s.size();i++){
if(isdigit(s[i])){
num=num*10+s[i]-'0';
}else if(s[i]=='+'||s[i]=='-'){
res+=sign*num;
sign=s[i]=='+'?1:-1;
num=0;
}else if(s[i]=='('){
st.push(res);
st.push(sign);
res=0;
sign=1;
}else if(s[i]==')'){
res+=sign*num;
num=0;
res*=st.top();
st.pop();
res+=st.top();
st.pop();
}else{
continue;
}
}
res+=sign*num;
return res;
}
9 Basic Calculator II
https://leetcode.com/problems/basic-calculator-ii/
>
int calculate(string s) {
stack<int> st;
int num=0;
char sign='+';
for(int i=0;i<s.size();i++){
if(isdigit(s[i])){
num=num*10+s[i]-'0';
}
if((!isdigit(s[i])&&s[i]!=' ')||i==s.size()-1){
if(sign=='+'){
st.push(num);
}else if(sign=='-'){
st.push(-num);
}else if(sign=='*'){
num=st.top()*num;
st.pop();
st.push(num);
}else{
num=st.top()/num;
st.pop();
st.push(num);
}
sign=s[i];
num=0;
}
}
int res=0;
while(!st.empty()){
res+=st.top();
st.pop();
}
return res;
}
10 Valid Palindrome
https://leetcode.com/problems/valid-palindrome/
>
bool isPalindrome(string s) {
int i=0,j=s.size()-1;
while(i<j){
while(i<s.size()&&!isalnum(s[i])) i++;
while(i<j&&j<s.size()&&!isalnum(s[j])) j--;
if(i<j&&tolower(s[i])!=tolower(s[j])) return false;
i++;
j--;
}
return true;
}
11 Decode Ways
https://leetcode.com/problems/decode-ways/
>
int numDecodings(string s) {
int n=s.size();
if(n==0) return 0;
vector<int> dp(n+1,0);
dp[n]=1;
dp[n-1]=s[n-1]=='0'?0:1;
for(int i=n-2;i>=0;i--){
if(dp[i]=='0') continue;
dp[i]=stoi(s.substr(i,2))<=26?dp[i+1]+dp[i+2]:dp[i+1];
}
return dp[0];
}
KMP algorithm
12 Shortest Palindrome
https://leetcode.com/problems/shortest-palindrome/
>
string shortestPalindrome(string s) {
string rev_s=s;
reverse(rev_s.begin(),rev_s.end());
string p=s+"#"+rev_s;
vector<int> match(p.size(),0);
for(int i=1;i<p.size();i++){
int j=match[i-1];
while(j>0&&p[i]!=p[j]) j=match[j-1];
match[i]=j+=p[i]==p[j];
}
return rev_s.substr(0,s.size()-match[p.size()-1])+s;
}
13 Implement strStr()
https://leetcode.com/problems/implement-strstr/
>
int strStr(string haystack, string needle) {
if(needle.size()==0) return 0;
vector<int> match=KMP(s);
int j=0;
for(i=0;i<haystack.size();i++){
while(j>0&&haystack[i]!=needle[j]) j=match[j-1];
j+=haystack[i]==needle[j];
if(j==needle.size()) return i-needle.size()+1;
}
return -1;
}
vector<int> KMP(string s){
vector<int> match(s.size(),0);
for(int i=1;i<s.size();i++){
int j=match[i-1];
while(j>0&&s[j]!=s[i]) j=match[j-1];
match[i]=j+=s[j]==s[i];
}
return match;
}
14 One Edit Distance
>
bool isOneEditDistance(string s, string t){
int len1=s.size(),len2=t.size();
if(abs(len1-len2)>1) return false;
for(int i=0;i<min(len1,len2);i++){
if(s[i]!=t[i]){
if(len1>len2){
if(s.substr(i+1)!=t.substr(i)) return false;
}else if(len1<len2){
if(s.substr(i)!=t.substr(i)) return fasle;
}else{
if(s.substr(i+1)!=t.substr(i+1)) return false;
}
}
}
return true;
}
15 Scramble String
https://leetcode.com/problems/scramble-string/
recursive solution
>
bool isScramble(string s1, string s2){
if(s1==s2) return true;
unordered_map<char,int> count;
for(auto c:s1) count[c]++;
for(auto c:s2) count[c]--;
for(auto it: count) if(it.second!=0) return false;
for(int i=1;i<s1.size();i++){
if(isScramble(s1.substr(0,i),s2.substr(0,i))&&isScramble(s1.substr(i),s2.substr(i)))
return true;
if(isScramble(s1.substr(0,i),s2.substr(s2.size()-i))
&&isScramble(s1.substr(i),s2.substr(0,s2.size()-i))) return true;
}
return false;
}
Dynamic Programming
>
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size()) return false;
if(s1==s2) return true;
int len=s1.size();
vector<vector<vector<bool> > > dp(len+1,vector<vector<bool> >(len,vector<bool>(len,false)));
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
if(s[i]==s[j]) dp[1][i][j]=true;
}
}
for(int l=2;l<=len;l++){
for(int i=0;i<=len-l;i++){
for(int j=0;j<=len-l;j++){
for(int k=1;k<len;k++){
dp[l][i][j]=dp[l][i][j]||(dp[k][i][j]&&dp[l-k][i+k][j+k]);
dp[l][i][j]=dp[l][i][j]||(dp[k][i][j+l-k]&&dp[l-k][i+k][j]);
}
}
}
}
return dp[len][0][0];
}
16 Word Ladder II
https://leetcode.com/problems/word-ladder-ii/
>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string> > ladders;
vector<string> ladder;
unordered_map<string,vector<string> > adj;
unordered_map<string,int> dist;
wordList.insert(beginWord);
wordList.insert(endWord);
for(auto word:wordList){
dist[word]=INT_MAX;
}
dist[beginWord]=0;
queue<string> q;
q.push(beginWord);
int minStep=INT_MAX;
while(!q.empty()){
string word=q.front();
q.pop();
int step=dist[word]+1;
if(step>minStep) break;
if(word==endWord) minStep=step;
for(int i=0;i<word.size();i++){
string newWord=word;
for(int j=0;j<26;j++){
if('a'+j==word[i]) continue;
newWord[i]='a'+j;
if(dist.count(newWord)==0) continue;
if(dist[newWord]<step) continue;
else if(dist[newWord]>step){
dist[newWord]=step;
q.push(newWord);
}
adj[word].push_back(newWord);
}
}
}
dfs(beginWord,endWord,adj,ladder,ladders);
return ladders;
}
void dfs(string word,string endWord,unordered_map<string,vector<string> >& adj,vector<string>& ladder, vector<vector<string> >& ladders){
ladder.push_back(word);
if(word==endWord){
ladders.push_back(ladder);
ladder.pop_back();
return;
}
for(auto node:adj[word]){
dfs(node,endWord,adj,ladder,ladders);
}
ladder.pop_back();
return;
}
17 Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/
>
class TrieNode {
public:
bool isWord;
vector<TrieNode*> children;
TrieNode(){
isWord=false;
children=vector<TrieNode*> (26,NULL);
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string word) {
TrieNode* cur=root;
for(auto c:word){
int id=c-'a';
if(!cur->children[id]) cur->children[id]=new TrieNode();
cur=cur->children[id];
}
cur->isWord=true;
}
// Returns if the word is in the trie.
bool search(string word) {
TrieNode* cur=root;
for(auto c:word){
int id=c-'a';
if(!cur->children[id]) return false;
cur=cur->children[id];
}
return cur->isWord;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* cur=root;
for(auto c:word){
int id=c-'a';
if(!cur->children[id]) return false;
cur=cur->children[id];
}
return true;
}
private:
TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");
18 Word Search II
https://leetcode.com/problems/word-search-ii/
Brute force: Time Limit Exceed
>
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
set<string> res;
for(int i=0;i<words.size();i++){
if(exist(board,words[i])) res.insert(words[i]);
}
vector<string> sol;
for(auto s:res) sol.push_back(s);
return sol;
}
bool exist(vector<vector<char>>& board, string word) {
if(board.empty()||board[0].empty()) return false;
vector<vector<bool> > visited(board.size(),vector<bool>(board[0].size(),false));
for(int i=0;i<board.size();i++){
for(int j=0;j<board[i].size();j++){
if(findword(board,i,j,visited,word,0)) return true;
}
}
return false;
}
bool findword(vector<vector<char> >& board,int i, int j, vector<vector<bool> >& visited, string word, int index){
if(start==word.size()) return true;
if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]=='#'||board[i][j]!=word[start]) return false;
char c=board[i][j];
board[i][j]='#';
if(backTracking(start+1,i+1,j,word,board)) return true;
if(backTracking(start+1,i-1,j,word,board)) return true;
if(backTracking(start+1,i,j+1,word,board)) return true;
if(backTracking(start+1,i,j-1,word,board)) return true;
board[i][j]=c;
return false;
}
Trie Tree Method
>
class TrieNode{
bool isWord;
vector<TrieNode*> children;
TrieNode(){
isWord=false;
children=vector<TrieNode*>(26,NULL);
}
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
if(words.size()==0||board.size()==0||board[0].size()==0) return res;
TrieNode* root=buildTrie(words);
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
backTracking(i,j,"",root,res,board);
}
}
return res;
}
void backTracking(int i,int j,string word,TrieNode* cur,vector<string>& res, vector<vector<char> >& board){
char c=board[i][j];
if(c=='#'||!cur->children[c-'a']) return;
cur=cur->children[c-'a'];
word=word+c;
if(cur->isWord){
res.push_back(word);
cur->isWord=false;
}
board[i][j]='#';
if(i>0) backTracking(i-1,j,word,cur,res,board);
if(i<board.size()-1) backTracking(i+1,j,word,cur,res,board);
if(j>0) backTracking(i,j-1,word,cur,res,board);
if(j<board[0].size()-1) backTracking(i,j+1,word,cur,res,board);
board[i][j]=c;
return;
}
TrieNode* buildTrie(vector<string>& words){
TrieNode* root=new TrieNode();
for(auto word:words){
TrieNode* cur=root;
for(auto c:word){
if(!cur->children[c-'a']) cur->children[c-'a']=new TrieNode();
cur=cur->children[c-'a'];
}
cur->isWord=true;
}
return root;
}
19 Add and Search Word - Data structure design
https://leetcode.com/problems/add-and-search-word-data-structure-design/
>
class TrieNode{
public:
bool isWord;
vector<TrieNode*> children;
TrieNode(){
isWord=false;
children=vector<TrieNode*>(26,NULL);
}
};
class WordDictionary{
public:
WordDictionary(){
root=new TrieNode();
}
void addWord(string word){
TrieNode* cur=root;
for(auto c:word){
if(!cur->children[c-'a']) cur->children[c-'a']=new TrieNode();
cur=cur->children[c-'a'];
}
cur->isWord=true;
}
bool searchWord(string word){
return query(word,root);
}
bool query(string word,TrieNode* root){
TrieNode* cur=root;
for(int i=0;i<word.size();i++){
if(cur&&word[i]!='.'){
if(!cur->children[word[i]-'a']) return false;
cur=cur->children[word[i]-'a'];
}else if(cur&&word[i]=='.'){
TrieNode* temp=cur;
for(int j=0;i<26;j++){
cur=temp->children[j];
if(query(word.substr(i+1),cur)) return true;
}
}else break;
}
return cur&&cur->isWord;
}
private:
TrieNode* root;
}
20 Distinct Subsequences
https://leetcode.com/problems/distinct-subsequences/
>
int numDistinct(string s, string t) {
int m=t.size(),n=s.size();
vector<vector<int> > dp(m+1,vector<int>(n+1,0));
for(int j=0;j<=n;j++) dp[0][j]=1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(t[i]==s[j]) dp[i+1][j+1]=dp[i][j]+dp[i+1][j];
else dp[i+1][j+1]=dp[i+1][j];
}
}
return dp[m][n];
}
>
int numDistinct(string s, string t) {
int m=t.size(),n=s.size();
vector<int> cur(1+m,0);
cur[0]=1;
for(int j=1;j<=n;j++){
int prev=1;
for(int i=1;i<=m;i++){
int temp=cur[i];
cur[i]=cur[i]+(s[j-1]==t[i-1]?prev:0);
prev=temp;
}
}
return cur[m];
}
21 Interleaving String
https://leetcode.com/problems/interleaving-string/
>
bool isInterleave(string s1, string s2, string s3) {
if(s1.size()+s2.size()!=s3.size()) return false;
int m=s1.size(),n=s2.size();
vector<vector<bool> > dp(1+m,vector<bool>(1+n,false));
for(int i=0;i<=m;i++){
for(int j=0;j<=n; j++){
if(i==0&&j==0){
dp[i][j]=true;
}else if(i==0){
dp[i][j]=dp[i][j-1]&&s2[j-1]==s3[i+j-1];
}else if(j==0){
dp[i][j]=dp[i-1][j]&&s1[i-1]==s3[i+j-1];
}else{
dp[i][j]=(dp[i-1][j]&&s1[i-1]==s3[i+j-1])||(dp[i][j-1]&&s2[j-1]==s3[i+j-1]);
}
}
}
return dp[m][n];
}
22 Edit Distance
https://leetcode.com/problems/edit-distance/
>
int minDistance(string word1, string word2) {
int m=word1.size(),n=word2.size();
vector<vector<int> > dp(1+m,vector<int>(1+n,0));
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=0;i<m;i++){
for(int j=0;j<n;j++){
if(word1[i]==word2[j]){
dp[i+1][j+1]=dp[i][j];
}else{
dp[i+1][j+1]=min(dp[i+1][j],min(dp[i][j],dp[i][j+1]))+1;
}
}
}
return dp[m][n];
}
>
int minDistance(string word1, string word2) {
int m=word1.size(),n=word2.size();
vector<int> cur(1+n,0);
for(int i=0;i<=n;i++){
cur[i]=i;
}
for(int i=1;i<=m;i++){
int prev=cur[0];
cur[0]=i;
for(int j=1;j<=n;j++){
int temp=cur[j];
if(word1[i-1]==word2[j-1]){
cur[j]=prev;
}else{
cur[j]=min(temp,min(prev,cur[j-1]))+1;
}
prev=temp;
}
}
return cur[n];
}
23 Palindrome Partitioning II
https://leetcode.com/problems/palindrome-partitioning-ii/
>
int minCut(string s) {
int n=s.size();
vector<int> cut(n,0);
vector<vector<bool> > isPal(n,vector<bool>(n,false));
for(int i=0;i<n;i++){
int minC=i;
for(int j=0;j<=i;j++){
if(s[j]==s[i]&&(j+1>i-1||isPal[j+1][i-1])){
isPal[j][i]=true;
minC=j==0?0:min(minC,cut[j-1]+1);
}
}
cut[i]=minC;
}
return cut[n-1];
}
>
int minCut(string s) {
int n=s.size();
vector<int> cut(n+1,0);
for(int i=0;i<=n;i++) cut[i]=i-1;
for(int i=0;i<n;i++){
for(int j=0;j<=i&&i+j<n&&i&&s[i-j]==s[i+j];j++){
cut[i+j+1]=min(cut[i+j+1],cut[i-j]+1);
}
for(int j=1;j<=i+1&&i+j<n&&s[i-j+1]==s[i+j];j++){
cut[i+j+1]=min(cut[i+j+1],cut[i-j+1]+1);
}
}
return cut[n];
}
24 Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
>
class Solution {
public:
string longestPalindrome(string s) {
int maxLen=0;
int start=0;
for(int i=0;i<s.size();i++){
isPalindrome(s,i,i,maxLen,start);
isPalindrome(s,i,i+1,maxLen,start);
}
return s.substr(start,maxLen);
}
void isPalindrome(string s, int i, int j, int &maxLen, int &start){
while(i>=0&&j<s.size()&&s[i]==s[j]){
i--;
j++;
}
if(j-i-1>maxLen){
maxLen=j-i-1;
start=i+1;
}
return;
}
};
25 Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/
>
string minWindow(string s, string t) {
int start=0,j=0,minLen=t.size(),len=t.size();
unordered_map<char,int> cnt;
for(auto c:t) cnt[c]++;
for(int i=0;i<s.size();i++){
if(cnt[s[i]]-->0) len--;
while(len==0){
if(i-j+1<minLen){
minLen=i-j+1;
start=j;
}
if(cnt[s[j++]]++==0) len++;
}
}
return minLen==INT_MAX?"":s.substr(start,minLen);
}
26 Group Anagrams
https://leetcode.com/problems/anagrams/
>
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string> > group;
for(auto s:strs){
string temp=s;
sort(temp.begin(),temp.end());
if(group.count(temp)>0) group[temp].push_back(s);
else group[temp]={s};
}
vector<vector<string> > res;
for(auto it:group){
res.push_back(it.second);
}
return res;
}
27 Word Break II
https://leetcode.com/problems/word-break-ii/
>
class Solution {
public:
unordered_map<string,vector<string> > m;
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
if(m.count(s)>0) return m[s];
vector<string> res;
if(wordDict.count(s)>0) res.push_back(s);
for(int i=1;i<s.size();i++){
string word=s.substr(0,i);
if(wordDict.count(word)>0){
vector<string> temp=combine(word,wordBreak(s.substr(i),wordDict));
res.insert(res.end(),temp.begin(),temp.end());
}
}
m[s]=res;
return res;
}
vector<string> combine(string word,vector<string> words){
for(int i=0;i<words.size();i++){
words[i]=word+" "+words[i];
}
return words;
}
};
28 Palindrome Partitioning
>
vector<vector<string>> partition(string s) {
vector<vector<string> > sols;
vector<string> sol;
vector<vector<bool> > isPal(s.size(),vector<bool>(s.size(),false));
for(int i=0;i<s.size();i++){
for(int j=0;j<=i;j++){
if(s[i]==s[j]&&(j+1>i-1||isPal[j+1][i-1])) isPal[j][i]=true;
}
}
backTracking(0,s,sol,sols,isPal);
return sols;
}
void backTracking(int start,string s, vector<string>& sol,vector<vector<string> >& sols,
vector<vector<bool> >& isPal){
if(start==s.size()){
sols.push_back(sol);
return;
}
for(int i=start;i<s.size();i++){
if(isPal[start][i]){
sol.push_back(s.substr(start,i+1-start));
backTracking(i+1,s,sol,sols,isPal);
sol.pop_back();
}
}
return;
}
29 Word Search
https://leetcode.com/problems/word-search/
>
bool exist(vector<vector<char>>& board, string word) {
for(int i=0;i<board.size();i++){
for(int j=0;j<board[i].size();j++){
if(backTracking(0,i,j,word,board)) return true;
}
}
return false;
}
bool backTracking(int k,int i,int j,string word,vector<vector<char> >& board){
if(k==word.size()) return true;
if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]=='#'||board[i][j]!=word[k]) return false;
char c=board[i][j];
board[i][j]='#';
bool exist=backTracking(k+1,i+1,j,word,board)||
backTracking(k+1,i-1,j,word,board)||
backTracking(k+1,i,j+1,word,board)||
backTracking(k+1,i,j-1,word,board);
board[i][j]=c;
return exist;
}
Return the path time complexity O(m*4^n)
>
vector<vector<pair<int,int> > > exist(vector<vector<char>>& board, string word) {
vector<pair<int,int> > path;
vector<vector<pair<int,int> > > paths;
for(int i=0;i<board.size();i++){
for(int j=0;j<board[i].size();j++){
if(DFS(0,i,j,path,paths,word,board)) return true;
}
}
return false;
}
void DFS(int k,int i,int j,vector<pair<int,int> >& path, vector<vector<pair<int,int> > > paths, string word,vector<vector<char> >& board){
if(k==word.size()){
paths.push_back(path);
return;
}
if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]=='#'||board[i][j]!=word[k]) return false;
char c=board[i][j];
board[i][j]='#';
path.push_back({i,j});
DFS(k+1,i+1,j,path,paths,word,board);
DFS(k+1,i-1,j,path,paths,word,board);
DFS(k+1,i,j+1,path,paths,word,board);
DFS(k+1,i,j-1,path,paths,word,board);
board[i][j]=c;
path.pop_back();
}
Trie Method
>
class TrieNode{
public:
bool isWord;
vector<TrieNode*> children;
vector<vector<pair<int,int> > > paths;
TrieNode(){
isWord=false;
children=vector<TrieNode*>(26,NULL);
}
};
vector<vector<pair<int,int> > > exist(vector<vector<char>>& board, string word) {
vector<pair<int,int> > path;
vector<vector<pair<int,int> > > paths;
TrieNode* root=trie(word);
return false;
}
void DFS(int k,int i,int j,vector<pair<int,int> >& path, vector<vector<pair<int,int> > > paths, string word,vector<vector<char> >& board){
if(k==word.size()){
paths.push_back(path);
return;
}
if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]=='#'||board[i][j]!=word[k]) return false;
char c=board[i][j];
board[i][j]='#';
path.push_back({i,j});
DFS(k+1,i+1,j,path,paths,word,board);
DFS(k+1,i-1,j,path,paths,word,board);
DFS(k+1,i,j+1,path,paths,word,board);
DFS(k+1,i,j-1,path,paths,word,board);
board[i][j]=c;
path.pop_back();
}
30 Wildcard Matching
https://leetcode.com/problems/wildcard-matching/
>
bool isMatch(string s, string p) {
vector<vector<bool> > dp(s.size()+1,vector<bool>(p.size()+1,false));
dp[0][0]=true;
for(int j=0;j<p.size();j++) dp[0][j+1]=dp[0][j]&&p[j]=='*';
for(int i=0;i<s.size();i++){
for(int j=0;j<p.size();j++){
if(p[j]!='*') dp[i+1][j+1]=dp[i][j]&&(s[i]==p[j]||p[j]=='?');
else dp[i+1][j+1]=dp[i+1][j]||dp[i][j+1];
}
}
return dp[s.size()][p.size()];
}
31 Regular Expression Matching
https://leetcode.com/problems/regular-expression-matching/
>
bool isMatch(string s, string p) {
vector<vector<bool> > dp(s.size()+1,vector<bool>(p.size()+1,false));
dp[0][0]=true;
for(int j=0;j<p.size();j++) dp[0][j+1]=(j==0&&p[j]=='*')||(j>0&&p[j]=='*'&&dp[0][j-1]);
for(int i=0;i<s.size();i++){
for(int j=0;j<p.size();j++){
if(p[j]!='*') dp[i+1][j+1]=dp[i][j]&&(s[i]==p[j]||p[j]=='.');
else dp[i+1][j+1]=j>0&&(dp[i+1][j-1]||((s[i]==p[j-1]||p[j-1]=='.')&&dp[i][j+1]));
}
}
return dp[s.size()][p.size()];
}
32 Longest Valid Parentheses
https://leetcode.com/problems/longest-valid-parentheses/
>
int longestValidParentheses(string s) {
stack<int> st;
int maxL=0;
int left=-1;
for(int i=0;i<s.size();i++){
if(s[i]=='(') st.push(i);
else{
if(st.emtpy()) left=i;
else{
st.pop();
if(st.empty()) maxL=max(maxL,i-left);
else maxL=max(maxL,i-st.top());
}
}
}
return maxL;
}
>
int longestValidParentheses(string s) {
int maxL=0;
vector<int> dp(s.size(),0);
for(int i=1;i<s.size();i++){
if(s[i]=='(') continue;
if(s[i-1]=='(') dp[i]=2+(i-2)>=0?dp[i-2]:0;
else{
if(i-1-dp[i-1]>=0&&s[i-1-dp[i-1]]=='(')
dp[i]=dp[i-1]+2+(i-2-dp[i-1]>=0)dp[i-2-dp[i-1]]:0;
}
maxL=max(maxL,dp[i]);
}
return maxL;
}
33 Valid Parentheses
https://leetcode.com/problems/valid-parentheses/
>
int longestValidParentheses(string s) {
int maxL=0;
vector<int> dp(s.size(),0);
for(int i=1;i<s.size();i++){
if(s[i]=='(') continue;
if(s[i-1]=='(') dp[i]=2+(i-2)>=0?dp[i-2]:0;
else{
if(i-1-dp[i-1]>=0&&s[i-1-dp[i-1]]=='(')
dp[i]=dp[i-1]+2+(i-2-dp[i-1]>=0)dp[i-2-dp[i-1]]:0;
}
maxL=max(maxL,dp[i]);
}
return maxL;
}
34 Valid Parentheses
https://leetcode.com/problems/valid-parentheses/
>
bool isValid(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='('||s[i]=='['||s[i]=='{') st.push(s[i]);
else{
if((s[i]==')'&&(st.empty()||st.top!='('))||
(s[i]==']'&&(st.empty()||st.top!='['))||
(s[i]=='}'&&(st.empty()||st.top!='{'))
) return false;
st.pop();
}
}
return st.empty();
}
35 Generate Parentheses
https://leetcode.com/problems/generate-parentheses/
>
vector<string> generateParenthesis(int n) {
vector<string> res;
generateParenthesis("",n,0,res);
return res;
}
void generateParenthesis(string s, int n, int m, vector<string>& res){
if(m==0&&n==0){
res.push_back(s);
return;
}
if(n>0) generateParenthesis(s+"(",n-1,m+1,res);
if(m>0) generateParenthesis(s+")",n,m-1,res);
return;
}
36 Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
>
map<char,vector<char> > m{{'2',{'a','b','c'}},{'3',{'d','e','f'}},{'4',{'g','h','i'}},{'5',{'j','k','l'}},{'6',{'m','n','o'}},{'7',{'p','q','r','s'}},{'8',{'t','u','v'}},{'9',{'w','x','y','z'}}};
vector<string> letterCombinations(string digits) {
vector<string> res;
if(digits.size()==0) return res;
backTracking("",0,digits,res);
return res;
}
void backTracking(string s,int n,string digits,vector<string>& res){
if(n==digits.size()){
res.push_back(s);
return;
}
for(auto c:m[digits[n]]){
backTracking(s+c,n+1,digits,res);
}
return;
}
37 Multiply Strings
https://leetcode.com/problems/multiply-strings/
>
string multiply(string num1, string num2) {
string res(num1.size()+num2.size(),'0');
for(int i=num1.size()-1;i>=0;i--){
int carry=0;
for(int j=num2.size()-1;j>=0;j--){
int value=res[i+j+1]-'0'+(num1[i]-'0')*(num2[j]-'0')+carry;
res[i+j+i]=value%10+'0';
carry=value/10;
}
res[i]+=carry;
}
size_t s=res.find_first_not_of("0");
if(s!=string::npos) res.substr(s);
return "0";
}
38 Substring with Concatenation of All Words
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
>
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
unordered_map<string,int> counts;
int m=s.size(),n=words.size(),len=words[0].size();
for(auto word:words) counts[word]++;
for(int i=0;i<=m-n*len;i++){
unordered_map<string,int> visited;
int j=0;
for(;j<n;j++){
string word=s.substr(i+j*len,len);
if(counts.count(word)){
visited[word]++;
if(visited[word]>counts[word]) break;
}else break;
}
if(j==n) res.push_back(i);
}
return res;
}
39 Ransom Note
https://leetcode.com/problems/ransom-note/
>
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> count;
for(auto c:ransomNote) count[c]++;
for(auto c:magazine) count[c]--;
for(auto it=count.begin();it!=count.end();it++){
if(it->second>0) return false;
}
return true;
}
40 First Unique Character in a String
https://leetcode.com/problems/first-unique-character-in-a-string/
>
int firstUniqChar(string s) {
unordered_map<char,pair<int,int> > count;
for(int i=0;i<s.size();i++){
count[s[i]].first++;
count[s[i]].second=i;
}
int res=INT_MAX;
for(auto it:count){
if(it.second.first==1) res=min(res,it.second.second);
}
return res==INT_MAX?-1:res;
}
41 Isomorphic Strings
https://leetcode.com/problems/isomorphic-strings/
>
bool isIsomorphic(string s, string t) {
if(s.size()!=t.size()) return false;
vector<int> map_s(256,0);
vector<int> map_t(256,0);
for(int i=0;i<s.size();i++){
if(map_s[s[i]]!=map_t[t[i]]) return false;
map_s[s[i]]=i+1;
map_t[t[i]]=i+1;
}
return true;
}
42 Word Pattern
https://leetcode.com/problems/word-pattern/
>
bool wordPattern(string pattern, string str) {
unordered_map<char,int> map_p;
unordered_map<string,int> map_s;
istringstream in(str);
int i=0,n=pattern.size();
for(string word;in>>word;i++){
if(i==n||map_p[pattern[i]]!=map_s[word]) return false;
map_p[pattern[i]]=i+1;
map_s[word]=i+1;
}
return i==n;
}
>
bool wordPattern(string pattern, string str) {
unordered_map<char,string> m;
unordered_set<string> words;
istringstream in(str);
int i=0,n=pattern.size();
for(string word;in>>word;i++){
if(i==n||(m.count(pattern[i])>0&&m[pattern[i]]!=word)||(m.count(pattern[i])==0&&words.count(word)>0))
return false;
m[pattern[i]]=word;
words.insert(word);
}
return i==n;
}
43 Bulls and Cows
https://leetcode.com/problems/bulls-and-cows/
>
string getHint(string secret, string guess) {
vector<int> map_s(10,0);
vector<int> map_g(10,0);
int bull=0,cow=0;
for(int i=0;i<secret.size();i++){
if(secret[i]==guess[i]) bull++;
else{
map_s[secret[i]-'0']++;
map_g[guess[i]-'0']++;
}
}
for(int i=0;i<10;i++){
cow+=min(map_s[i],map_g[i]);
}
return to_string(bull)+"A"+to_string(cow)+"B";
}
44 Find the Difference
https://leetcode.com/problems/find-the-difference/
>
char findTheDifference(string s, string t) {
unordered_map<char,int> cnt;
for(auto c:t) cnt[c]++;
for(auto c:s) cnt[c]--;
for(auto it:cnt) if(it.second>0) return it.first;
return '#';
}
45 Valid Anagram
https://leetcode.com/problems/valid-anagram/
>
bool isAnagram(string s, string t) {
unordered_map<char,int> cnt;
for(auto c:s) cnt[c]++;
for(auto c:t) cnt[c]--;
for(auto it:cnt) if(it.second!=0) return false;
return true;
}
46 Fraction to Recurring Decimal
https://leetcode.com/problems/fraction-to-recurring-decimal/
>
string fractionToDecimal(int numerator, int denominator) {
if(numerator==0) return "0";
string res;
if(numerator>0^denominator>0) res+='-';
long n=numerator>0?(long)numerator:(-1)*(long)numerator;
long d=denominator>0?(long)denominator:(-1)*(long)denominator;
res+=to_string(n/d);
long r=n%d;
if(r==0) return res;
res+='.';
r*=10;
unordered_map<int,int> pos;
while(r!=0){
if(pos.count(r)>0){
res.insert(pos[r],1,'(');
res+=')';
break;
}
pos[r]=res.size();
res+=to_string(r/d);
r=(r%d)*10;
}
return res;
}
47 Repeated DNA Sequences
https://leetcode.com/problems/repeated-dna-sequences/
>
vector<string> findRepeatedDnaSequences(string s) {
vector<int> res;
unordered_set<int> seqOnce;
unordered_set<int> seqTwice;
int n=s.size();
vector<int> map(26,0);
map['A'-'A']=0;
map['C'-'A']=1;
map['G'-'A']=2;
map['T'-'A']=3;
for(int i=0;i<n-9;i++){
int temp=0;
for(int j=i;j<i+10;j++){
temp<<=2;
temp|=map[s[j]-'A'];
}
if(!seqOnce.insert(temp).second&&seqTwice.insert(temp)){
res.push_back(s.substr(i,10));
}
}
return res;
}
48 Is Subsequence
https://leetcode.com/problems/is-subsequence/
DP : Time Limit Exceed
>
bool isSubsequence(string s, string t) {
int m=s.size(),n=t.size();
vector<vector<bool> > dp(1+m,vector<bool>(1+n,false));
for(int j=0;j<=n;j++) dp[0][j]=true;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=dp[i][j-1];
}
}
return dp[m][n];
}
Two Pointer
>
bool isSubsequence(string s, string t) {
if(s.size()==0) return true;
if(t.size()==0) return false;
int ids=0,idt=0;
while(idt<t.size()){
if(s[ids]==t[idt]){
ids++;
if(ids==s.size()) return true;
}
idt++;
}
return false;
}
bool isSubsequence(string s, string t) {
int i=0,j=0;
while(i<s.size()){
while(j<t.size()&&s[i]!=t[j]) j++;
if(j==t.size()) return false;
i++;
j++;
}
return true;
}
49 Different Ways to Add Parentheses
https://leetcode.com/problems/different-ways-to-add-parentheses/
>
vector<int> diffWaysToCompute(string input) {
vector<int> res;
for(int i=0;i<input.size();i++){
if(input[i]=='+'||input[i]=='-'||input[i]=='*'){
vector<int> result1=diffWaysToCompute(input.substr(0,i));
vector<int> result2=diffWaysToCompute(input.substr(i+1));
for(auto num1:result1){
for(auto num2:result2){
if(input[i]=='+'){
res.push_back(num1+num2);
}else if(input[i]=='-'){
res.push_back(num1-num2);
}else{
res.push_back(num1*num2);
}
}
}
}
}
if(res.empty()){
res.push_back(stoi(input));
}
return res;
}
>
vector<int> diffWaysToCompute(string input) {
vector<int> diffWaysToCompute(string input) {
unordered_map<string,vector<int> > diffWays;
vector<int> res=compute(input,diffWays);
return res;
}
vector<int> compute(string input, unordered_map<string,vector<int> >& diffWays){
if(diffWays.count(input)) return diffWays[input];
vector<int> res;
for(int i=0;i<input.size();i++){
if(input[i]=='+'||input[i]=='-'||input[i]=='*'){
string input1=input.substr(0,i);
string input2=input.substr(i+1);
vector<int> result1,result2;
if(diffWays.count(input1)){
result1=diffWays[input1];
}else{
result1=compute(input1,diffWays);
}
if(diffWays.count(input2)){
result2=diffWays[input2];
}else{
result2=compute(input2,diffWays);
}
for(auto num1:result1){
for(auto num2:result2){
if(input[i]=='+'){
res.push_back(num1+num2);
}else if(input[i]=='-'){
res.push_back(num1-num2);
}else{
res.push_back(num1*num2);
}
}
}
}
}
if (res.empty())
res.push_back(stoi(input));
diffWays[input]=res;
return res;
}
50 Read N Characters Given Read4
READ FUNCTION WILL BE CALLED ONCE FOR EACH TEST CASE
>
int read(char *buf, int n) {
bool eof=false;
int total=0;
int cnt;
char temp[4];
while(!eof||total<n){
cnt=read4(tmp);
eof=cnt<4;
cnt=min(cnt,n-total);
for(int i=0;i<cnt;i++){
buf[total++]=temp[i];
}
}
return total;
}
51 Sudoku Solver
https://leetcode.com/problems/sudoku-solver/
>
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
bool solve(vector<vector<char> >& board){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]!='.') continue;
for(char c='1';c<='9';c++){
if(isValid(board,i,j,c)){
board[i][j]=c;
if(solve(board)){
return true;
}else{
board[i][j]='.';
}
}
}
return false;
}
}
return true;
}
bool isValid(vector<vector<char> >& board,int i, int j, char c){
for(int row=0;row<9;row++){
if(board[row][j]==c) return false;
}
for(int col=0;col<9;col++){
if(board[i][col]==c) return false;
}
for(int row=(i/3)*3;row<(i/3)*3+3;row++){
for(int col=(j/3)*3;col<(j/3)*3+3;col++){
if(board[row][col]==c) return false;
}
}
return true;
}
52 Remove K Digits
https://leetcode.com/problems/remove-k-digits/
>
string removeKdigits(string num, int k) {
int i=0,n=nums.size();
string res;
int drop=k;
for(;i<n;i++){
while(drop&&res.size()&&res.back()>num[i]){
drop--;
res.pop_back();
}
res.push_back(num[i]);
}
res.resize(n-k);
i=0;
while(res[i]=='0'&&i<n-1){
i++;
}
return res.substr(i);
}
53 Decode String
https://leetcode.com/problems/decode-string/
>
string decodeString(string s) {
stack<int> cnt;
stack<string> str;
string res="";
int i=0;
while(i<s.size()){
if(isdigit(s[i])){
int num=s[i]-'0';
while(isdigit(s[++i])){
num=num*10+s[i]-'0';
}
cnt.push(num);
}else if(s[i]=='['){
str.push(res);
res="";
i++;
}else if(s[i]==']'){
string temp=str.top();
str.pop();
int k=cnt.top();
cnt.pop();
for(int j=0;j<k;j++){
temp += res;
}
res=temp;
i++;
}else{
res+=s[i++];
}
}
return res;
}
>
string decodeString(string s) {
int i=0;
return helper(s,i);
}
string helper(string s, int &i){
string res="";
while(i<s.size()&&s[i]!=']'){
if(!isdigit(s[i])){
res+=s[i++];
}else{
int k=s[i++]-'0';
while(isdigit(s[i])) k=k*10+s[i++]-'0';
i++;
string temp=helper(s,i);
i++;
while(k--){
res+=temp;
}
}
}
return res;
}
>
string decodeString(string s) {
int i=0;
return helper(s,i);
}
string helper(string s, int &i){
string res="";
while(i<s.size()&&s[i]!=']'){
if(!isdigit(s[i])){
res+=s[i++];
}else{
int k=s[i++]-'0';
while(isdigit(s[i])) k=k*10+s[i++]-'0';
i++;
string temp=helper(s,i);
i++;
while(k--){
res+=temp;
}
}
}
return res;
}
54 Longest Substring with At Least K Repeating Characters
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
>
int longestSubstring(string s, int k) {
return helper(s,0,s.size(),k);
}
int helper(string s, int low, int high, int k){
if(low>=high||high-low<k) return 0;
unordered_map<char,int> cnt;
for(int i=low;i<high;i++) cnt[s[i]]++;
int i=low,j,maxLen=0;
while(i<high){
while(i<high&&cnt[s[i]]<k) i++;
j=i;
while(j<high&&cnt[s[j]]>=k) j++;
if(i==low&&j==high) return high-low;
maxLen=max(maxLen,helper(s,i,j,k));
i=j;
}
return maxLen;
}
>
int longestSubstring(string s, int k) {
return helper(s,0,s.size(),k);
}
int helper(string s, int low, int high, int k){
if(low>=high||high-low<k) return 0;
unordered_map<char,int> cnt;
for(int i=low;i<high;i++) cnt[s[i]]++;
for(auto it:cnt){
if(it.second<k){
for(int i=low;i<high;i++){
if(s[i]==it.first){
int left=helper(s,low,i,k);
int right=helper(s,i+1,high,k);
return max(left,right);
}
}
}
}
return high-low;
}
55 find longest sequence in Dictionary
Given a function to decide bool inDic(string input), find the max length for a sequence in a string that is in the dictionary
>
/* bool inDic(string input)*/
int longestSequence(string s){
vector<string> res;
int maxLen=0;
for(int i=0;i<s.size();i++){
string temp=””;
vector<int> seqs;
for(auto t: sequence){
temp=t;
temp+=s[i];
if(isDic(temp)){
seqs.push_back(temp);
maxLen=max(maxLen,temp.size());
}
}
res.insert(res.end(),seqs.begin(),seqs.end());
}
return maxLen;
}
56 Reconstruct Original Digits from English
https://leetcode.com/problems/reconstruct-original-digits-from-english/
>
string originalDigits(string s) {
vector<int> cnt(10,0);
for(auto c:s){
if(c=='z') cnt[0]++;
if(c=='w') cnt[2]++;
if(c=='u') cnt[4]++;
if(c=='x') cnt[6]++;
if(c=='g') cnt[8]++;
if(c=='o') cnt[1]++; /* zero, one, two, four: 1 'o' */
if(c=='h') cnt[3]++; /* three,eight: 1 'h' */
if(c=='v') cnt[5]++; /* five, seven: 1 'v' */
if(c=='s') cnt[7]++; /* six, seven: 1 's' */
if(c=='i') cnt[9]++; /* five, six, eight, nine: 1 'n' */
}
cnt[1]-=cnt[0]+cnt[2]+cnt[4];
cnt[3]-=cnt[8];
cnt[7]-=cnt[6];
cnt[5]-=cnt[7];
cnt[9]-=cnt[5]+cnt[6]+cnt[8];
string res="";
for(int i=0;i<10;i++){
for(int j=0;j<cnt[i];j++){
res+=to_string(i);
}
}
return res;
}
57 String to Integer (atoi)
https://leetcode.com/problems/string-to-integer-atoi/
>
int myAtoi(string str) {
long res=0;
int sign=1;
int i=0;
while(i<str.size()&&str[i]==' ') i++;
if(str[i]=='-'||str[i]=='+'){
sign=str[i++]=='-'?-1:1;
}
while(i<str.size()&&str[i]>='0'&&str[i]<='9'){
res=res*10+str[i++]-'0';
if(res*sign>INT_MAX) return INT_MAX;
else if (res*sign<INT_MIN) return INT_MIN;
}
return res*sign;
}
58 palindrome permutation II
---
>
vector<string> generatePalindromes(string s){
vector<char> list;
vector<string> res;
char mid=’’;
int odd=0;
map<char,int> cnt;
for(char c:s){
cnt[c]++;
odd+=cnt[c]%2==1?1:-1;
}
if(odd>1) return res;
for(auto it: cnt){
if(it->second==1) mid=it->first;
for(int i=0;i<it->second/2;i++){
list.push_back(it->first);
}
}
vector<bool> visited(list.size(),false);
string perm=””;
generatePermutations(0,list,mid,perm,res,visited);
return res;
}
void generatePermutations(int k, vector<char> list, char mid, string& perm, vector<string>& res,
vector<bool>& visited){
if(k==list.size()){
string temp=perm;
reverse(temp.begin(),temp.end());
res.push_back(perm+mid+temp);
return;
}
for(int i=0;i<list.size();i++){
if(visited[i]==true) continue;
if(i>0 && list[i]==list[i-1]&&!visited[i-1]) continue;
visited[i]=true;
perm.push_back(list[i]);
generatePermutations(k+1,list,mid,perm,res,visited);
visited[i]=false;
perm.pop_back();
}
}
59 ZigZag Conversion
https://leetcode.com/problems/zigzag-conversion/
---
>
string convert(string s, int numRows) {
vector<string> strs(numRows);
string res;
int i=0;
while(i<s.size()){
for(int j=0;i<s.size()&&j<numRows;j++){
strs[j].push_back(s[i++]);
}
for(int j=numRows-2;i<s.size()&&j>0;j--){
strs[j].push_back(s[i++]);
}
}
for(auto str:strs){
res+=str;
}
return res;
}
60 valid Word Abbreviation
---
>
bool validWordAbbreviation(string word, string abbr) {
int i=0;
int j=0;
while(i<abbr.size()){
int cnt=0;
while(i<abbr.size()&&isdigit(abbr[i])){
if(abbr[i]=='0'&&cnt==0) return false;
cnt=cnt*10+abbr[i++]-'0';
}
j+=cnt;
if(i<abbr.size()&&isalpha(abbr[i])){
if(j>=word.size()) return false;
else if(abbr[i]!=word[j]) return false;
else{
i++;
j++;
}
}
}
return cnt==word.size();
}
61 unique Word Abbreviation
---
>
class wordAbbr{
public:
wordAbbr(vector<string>& dict){
for(auto str:dict){
string abbr=str.size()<=2?str:(str[0]+to_string(str.size()-2)+str.back()); abbr2word[abbr].insert(str);
}
}
bool isUnique(string word){
string abbr=word.size()<=2?word:(word[0]+to_string(word.size()-2)+word.back());
return abbr2word[abbr].count(word)==abbr2word[abbr].size();
}
private:
unordered_map<string,set<string> > abbr2word;
};
62 Generalized Abbreviation
---
>
vector<string> generalizedAbbreviation(string word){
vector<string> res;
helper(word,0,0,"",res);
return res;
}
void helper(string word, int k,int cnt,string abbr,vector<string>& res){
if(k==word.size()){
abbr+=(cnt==0?""+to_string(cnt));
res.push_back(abbr);
return;
}
helper(word,k+1,0,abbr+(cnt==0?word[k]:to_string(cnt)+word[k]),res);
helper(word,k+1,cnt+1,abr,res);
}
63 Strobogrammatic Number I
---
>
bool isStrobogrammatic(string num){
int i=0,j=num.size();
while(i<=j){
if(!((num[i]=='0'&&num[j]=='0')
||(num[i]=='1'&&num[j]=='1')
||(num[i]=='8'&&num[j]=='8')
||(num[i]==’6’&&num[j]==’9’)
||(num[i]==’9’&&num[j]==’6’)
)) return false;
i++;j--;
}
return true;
}
64 Strobogrammatic Number II
---
>
vector<string> findStrobogrammatic(int n){
return helper(n,n);
}
vector<string> helper(int n, int m){
if(n==0) return {“”};
if(n==1) return {“0”,”1”,”8”};
vector<string> list=helper(n-2,m);
vector<string> res;
for(auto s: list){
if(n!=m) res.push_back(“0”+s+”0”);
res.push_back(“1”+s+”1”);
res.push_back(“8”+s+”8”);
res.push_back(“6”+s+”9”);
res.push_back(“9”+s+”6”);
}
return res;
}
---
>
vector<string> findStrobogrammatic(int n){
if(n==0) return “”;
if(n==1) return {“0”,”1”,”8”};
vector<int> res={“”};
if(n%2==1) res={“0”,”1”,”8”};
for(int i=n%2;i<=n;i+=2){
vector<int> temp;
for(auto s: res){
if(i!=n) temp.push_back(“0”+s+”0”);
temp.push_back(“1”+s+”1”);
temp.push_back(“8”+s+”8”);
temp.push_back(“6”+s+”9”);
temp.push_back(“9”+s+”6”);
}
res=temp;
}
return res;
}
65 Strobogrammatic Number III
---
>
vector<pair<char,char> > pairs{{‘0’,’0’},{‘1’,’1’},{‘8’,’8’},{‘6’,’9’},{‘9’,’6’}};
int strobogrammaticInRange(string low, string high){
int cnt=0;
for(int len=low.size();len<=high.size();len++){
dfs(low, high, 0, len-1, “”,cnt);
}
return cnt;
}
void dfs(string low,string high, int left, int right, string num, int& cnt){
if(left>right){
if(stoi(num)<stoi(low)||stoi(num)>stoi(high)) return;
cnt++;
return;
}
for(auto p:pairs){
if(num.size()>1&&num[0]==’0’) continue;
if(left==right&&p.first!=p.second) continue;
dfs(low,high,left+1,right-1,p[0]+num+p[1],cnt);
}
}
66 Valid Word Squares
---
>
bool validWordSquare(vector<string> words){
if(words.size()==0||words[0].size()==0) return true;
int n=words.size();
for(int i=0;i<n;i++){
int m=words[i].size();
for(int j=0;j<m;j++){
if(j>=n||words[j].size()<=i||words[j][i]!=words[i][j]) return false;
}
}
return true;
}
67 Word Squares
---
>
class TrieNode{
public:
vector<string> prefix2word;
vector<TrieNode*> children;
TrieNode(){
children=vector<TrieNode*>(26,NULL);
}
};
class Trie{
public:
TrieNode *root;
Trie(vector<string> words){
root=new TrieNode();
for(auto word:words){
TrieNode *cur=root;
for(auto c: word){
if(!cur->children[c-'a']) cur->children[c-'a']=new TrieNode();
cur=cur->children[c-'a'];
cur->prefix2word.push_back(word);
}
}
}
vector<string> wordsWithPrefix(string prefix){
vector<string> res;
TrieNode *cur=root;
for(auto c:prefix){
cur=cur->children[c-'a'];
if(!cur) return res;
}
res=cur->prefix2word;
return res;
}
};
vector<vector<string> > wordSquares(vector<string> words){
vector<vector<string> > sols;
vector<string> sol;
if(words.size()==0||words[0].size()==0) return sol;
Trie trie=new Trie(words);
int n=words[0].size();
for(auto word:words){
sol.push_back(word);
dfs(n,sol,sols,trie);
sol.pop_back();
}
return sols;
}
void dfs(int n,vector<string>& sol, vector<vector<string> >& sols, Trie* trie){
if(sol.size()==n){
sols.push_back(sol);
return;
}
string prefix="";
for(auto word:sol){
prefix+=word[sol.size()];
}
for(auto word:trie->wordsWithPrefix(prefix)){
sol.push_back(word);
dfs(n,sol,sols,trie);
sol.pop_back();
}
}
68 Word Pattern II
---
>
bool wordPatternMatch(string pattern, string str){
unordered_map<char,string> m;
unordered_set<string> s;
return match(pattern,0,str,0,m,s);
}
bool match(string pattern,int i, string str, int j, unordered_map<char,string>& m, unordered_set<string>& s){
if(i==pattern.size()&&j==str.size()) return true;
if(i==pattern.size()||j==str.size()) return false;
char c=pattern[i];
if(m.count(c)>0){
string word=m[c];
if(word!=str.substr(j,word.size())) return false;
else return match(pattern,i+1,str,j+word.size(),m,s);
}
for(int k=j;k<str.size();k++){
string word=str.substr(i,k-j+1);
if(s.count(word)>0) continue;
m[c]=word;
s.insert(word);
if(isMatch(pattern,i+1,str,k+1,m,s)) return true;
m.erase(c);
s.erase(word);
}
return false;
}
69 Find Words that can be combined from dictionary of characters
---
>
vector<string> combineWords(vector<string>& words, vector<char>& dict){
vector<string> res;
unordered_map<char,int> cnt;
for(auto c:dict) cnt[c]++;
for(auto word:words){
int i=0;
unordered_map<char,int> counter=cnt;
for(;i<word.size();i++){
if(counter.count(word[i])==0&&counter.count('?')==0) break;
else if(counter.count(word[i])==0&&counter.count('?')>0){
if(--counter['?']==0) counter.erase('?');
}else{
if(--counter[word[i]]==0) counter.erase(word[i]);
}
}
if(i==word.size()) res.push_back(word);
}
return res;
}
70 Longest Consecutive Substring
---
>
string longestConsecutiveSubstring(string s) {
int start=0;
int maxLen=0;
int i=0;
while(i<s.size()){
int j=i;
char c=s[i++];
while(i<s.size()&&s[i]==s[i-1]+1) i++;
if(i-j>maxLen){
maxLen=i-j;
start=j;
}
}
return s.substr(start,maxLen);
}
71 Longest Common Prefix
---
>
string longestCommonPrefix(vector<string>& strs) {
string res="";
if(strs.size()==0) return res;
for(int i=0;i<strs[0].size();i++){
for(int j=1;j<strs.size();j++){
if(strs[j].size()<=i||strs[j][i]!=strs[0][i]) return res;
}
res+=strs[0][i];
}
return res;
}
72 Expression Add Operators
---
>
vector<string> addOperators(string num, int target) {
vector<string> res;
helper(res,"",num,target,0,0,0);
return res;
}
void helper(vector<string>& res, string ans,string num,int target, int pos, long eval,long multed){
if(pos==num.size()){
if(eval==target) res.push_back(ans);
return;
}
for(int i=pos;i<num.size();i++){
if(i!=pos&&num[pos]=='0') break;
long cur=stol(num.substr(pos,i+1-pos));
if(pos==0) helper(res,ans+to_string(cur),num,target,i+1,cur,cur);
else{
helper(res,ans+'+'+to_string(cur),num,target,i+1,eval+cur,cur);
helper(res,ans+'-'+to_string(cur),num,target,i+1,eval-cur,-cur);
helper(res,ans+'*'+to_string(cur),num,target,i+1,eval-multed+multed*cur,multed*cur);
}
}
}
73 Read N Characters Given Read4
---
>
int read(char* buf, int n){
int total=0;
bool eof=false;
char temp[4];
int cnt;
while(!eof&&total<n){
cnt=read4(temp);
if(cnt<4) eof=true;
cnt=min(cnt,n-total);
for(int i=0;i<cnt;i++) buf[total++]=temp[i];
}
return total;
}
74 Read N Characters Given Read4
---
>
class read{
public:
int read(char* buf, int n){
int total=0;
char temp[4];
int cnt;
while(!eof&&total<n){
cnt=read4(temp);
if(cnt<4) eof=true;
for(int i=0;i<cnt;i++) q.push(temp[i]);
}
int k=min(q.size(),n);
for(int i=0;i<k;i++){
buf[total++]=q.front();
q.pop()
}
return total;
}
private:
queue<char> q;
bool eof=false;
};