LeetCode: Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

   bool isNumber(const char *s) {  
     int n = strlen(s);  
     int i = 0;  
     while(i<n && (s[i] == ' ' || s[i] == '\t'))i++;  
     if(i==n)return false;  
     int j = n-1;  
     while (j >= 0 && (s[j] == ' ' || s[j] == '\t'))j--;  
   
     s = s+i;  
     n = j-i+1;  
     if (n == 1)if(s[0] <='9' && s[0] >= '0')return true; else return false;  
   
     if (s[0] == '-' || s[0] == '+'){s++;n--;}  
     if (s[n-1] == '+' || s[n-1] == '-')return false;  
   
     bool res = true, dot = false, exp = false, number = false, sign = false;  
   
     for (i = 0; i < n; i++)  
     {  
       if(i==0 && (s[i] == '+' || s[i] == '-')){return false;}  
       else if ((s[i] == '+' || s[i] == '-') && s[i-1] != 'e') {return false;}  
       else if (s[i] == '+' || s[i] == '-')if(sign)return false; else sign = true;  
       else if(s[i] == '.'){  
         if (exp == true)return false;  
         if(dot == false)dot = true;  
         else return false;  
       }  
       else if (s[i] == 'e')  
       {  
         if (dot == true && number == false)return false;  
         if (i==0 || i== n-1 || exp == true)return false;  
         exp = true;  
       }  
       else if (s[i] < '0' || s[i] > '9'){return false;}  
       else number = true;  
     }  
   
     if(number == false)return false;  
   
     return res;  
   }  

LeetCode: 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, and there exists one unique longest palindromic substring.

   string longestPalindrome(string s) {  
     int n = s.length();  
     if(n<=1)return s;  
   
     int v[2][n];  
     int longest = 1, lindex = 0;  
   
     for (int i = 0; i < n; i++)v[1][i] = 1;  
   
     for (int i = 0; i < n-1; i++)  
       if(s[i] == s[i+1]){  
         lindex = i;  
         longest = 2;  
         v[0][i] = 1;  
       }  
       else v[0][i] = 0;  
   
     for ( int l = 3; l <= n; l++)  
     {  
       for (int i = 0; i+l-1 < n; i++)  
       {  
         int j = i+l-1;  
         if(v[l&1][i+1] && s[i] == s[j]){  
           lindex = i;  
           longest = l;  
           v[l&1][i] = 1;  
         }  
         else  
           v[l&1][i] = 0;  
       }  
     }  
   
     return s.substr(lindex, longest);  
   }  

LeetCode: 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".

   #define tr(c,it) for(decltype((c).begin()) (it) = (c).begin(); (it) != (c).end(); (it)++)  
   
   string convert(string s, int nRows) {  
     int n = s.length();  
     vector<string> v(nRows);  
     int j = 0, increase = 1;  
     if(nRows == 1)return s;  
     for (int i = 0; i < n; i++)  
     {  
       if(increase)  
       {  
         v[j++] += s[i];  
         if(j == nRows){j -= 2;increase = 0;}  
       }  
       else  
       {  
         v[j--] += s[i];  
         if(j < 0){j += 2;increase = 1;}  
       }  
     }  
     string res;  
     tr(v, it)  
     {  
       res += *it;  
     }  
     return res;  
   }  

LeetCode: 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.

   int lengthOfLongestSubstring(string s) {  
     int res = 0, start = 0;  
     int n = s.length();  
     vector<int> h(256, -1);  
   
     for (int i = 0; i < n; i++)  
     {  
       if (h[s[i]] != -1)  
       {  
         while(s[start] != s[i]){  
           h[s[start]] = -1;  
           start++;  
         }  
         start++;  
       }  
       else  
       {  
         if (res < i-start+1)res = i-start+1;  
         h[s[i]] = i;  
       }  
     }  
   
     return res;  
   }  

LeetCode: 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.

   int atoi(const char *str) {  
     if(!str)return 0;  
       
     int sign = 1, i = 0,prev;  
     long long res = 0;  
       
     while(str[i] == ' ' || str[i] == '\t')i++;  
       
     if(str[i] == '-'){sign = -1;i++;}  
     else if (str[i] == '+')i++;  
       
     while(str[i])  
     {  
       int x = str[i]-48;  
       if(x<0 || x>9 )return (res*sign);prev = res;  
       res = (res<<3) + (res<<1) + x;  
       if(res > 2147483647){if(sign == -1)return -2147483648; else return 2147483647;}   
       i++;  
     }  
     return ((int)res*sign);  
   }  

LeetCode: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

   string longestCommonPrefix(vector<string> &strs) {  
     int n = strs.size();  
     if (n == 0){string s; return s;}  
     if (n == 1){return strs[0];}  
     int length = 0;  
     int x = strs[0].length();  
     string res = strs[0];  
     for (int i = 1; i < n; i++)  
     {  
       int y = strs[i].length();  
       if(y < x)x = y;  
     }  
     bool success;  
     for (int i = 0; i < x; i++)  
     {  
       for (int j = 1; j<n; j++)  
       {  
         success = false;  
         if(strs[0][i] != strs[j][i])  
         {  
           break;  
         }  
         else  
           success = true;  
       }  
       if(success)length++;  
       else break;  
     }  
     return res.substr(0,length);  
   }  

LeetCode: 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.

   typedef vector<string> vs;  
   
   void letterCombinationsUtil(string digits, vs &res, vs &list, int cur, int n, string &s)  
   {  
     if(cur == n)  
     {  
       res.push_back(s);  
       return;  
     }  
     string &str = list[digits[cur] - '0'];  
     int x = str.length();  
     for (int i = 0; i < x; i++)  
     {  
       s[cur] = str[i];  
       letterCombinationsUtil(digits, res, list, cur+1, n, s);  
     }  
   }  
   
   vector<string> letterCombinations(string digits) {  
     vector<string> list = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};   
     vector<string> res;  
     int n = digits.length();  
     if(n == 0){res.push_back("");return res;}  
     string s;  
     for (int i = 0; i <n; i++)s += '0';  
     letterCombinationsUtil(digits, res, list, 0, n, s);  
     return res;  
   }  

LeetCode: 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.

   bool isValid(string s) {  
     stack<char> S;  
     int n = s.length();  
   
     for(int i = 0; i < n; i++)  
     {  
       if(s[i] == '(' || s[i] == '{' || s[i] == '[')S.push(s[i]);  
       else if (s[i] == ')' || s[i] == '}' || s[i] == ']')  
       {  
         if(S.empty())return false;  
         char t = S.top();  
         S.pop();  
         if((s[i] == ')' && t!= '(') ||  
           (s[i] == '}' && t!= '{') ||  
           (s[i] == ']' && t!= '[') )return false;  
       }  
     }  
     if(!S.empty())return false;  
     return true;  
   }  

LeetCode: 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:

"((()))", "(()())", "(())()", "()(())", "()()()"

   void generateParenthesisRecurse(string &s, int x, int y, int n, vector<string> &v)  
   {  
     if(y>x)return;  
     if (x+y == n)  
     {  
       if(x==y)  
         v.push_back(s);  
       return;  
     }  
     s[x+y] = '(';  
     generateParenthesisRecurse(s, x+1, y, n, v);  
     s[x+y] = ')';  
     generateParenthesisRecurse(s, x, y+1, n, v);  
   }  
   
   vector<string> generateParenthesis(int n) {  
     vector<string> V;  
     string s;  
     for (int i = 0; i<n*2; i++)s+='(';  
     generateParenthesisRecurse(s, 0, 0, n*2, V);  
     return V;  
   }  

LeetCode: Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

   void ComputPrefix(char* pattern,int pre[], int n)  
   {  
     memset(pre, 0, n);  
     int len = 0;  
     pre[len] = 0;  
     int i = 1;  
     while(i<n)  
     {  
       if(pattern[i] == pattern[len])  
       {  
         len++;  
         pre[i]=len;  
         i++;  
       }  
       else  
       {  
         if(len>0)  
         {  
           len = pre[len-1];  
         }  
         else  
         {  
           pre[i] = 0;  
           i++;  
         }  
       }  
     }  
   }  

   char *KMP(char *haystack, char *needle)  
   {  
     int n = strlen(needle);  
     int m = strlen(haystack);  
     if(n==0)return haystack;  
     int *pre = new int[n];  
     ComputPrefix(needle, pre,n);  
     int i = 0, j = 0;  
     for (; i < m;)  
     {  
       if(haystack[i] == needle[j])  
       {  
         if(j == n-1)  
         {  
           return (&haystack[i-n+1]);  
         }  
         j++;  
         i++;  
       }  
       else  
       {  
         if(j > 0)  
           j = pre[j-1];  
         else  
         {  
           i++;  
         }  
       }  
     }  
     return NULL;  
   }  

   char *strStr(char *haystack, char *needle) {  
     return KMP(haystack,needle);  
   }  

LeetCode: Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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 sequence.

Note: The sequence of integers will be represented as a string.

   string StringPrep(string s)  
   {  
     string res;  
     int d = s.length();  
     for(int i = 0; i<d;)  
     {  
       char c = s[i];  
       int j = i+1;  
       while(j<d && s[j] == s[i])j++;  
       res += j-i + '0';  
       res += s[i];  
       i += j-i;  
     }  
     return res;  
   }  

   string countAndSay(int n) {  
     string s = "1";  
     for (int i = 1; i <n; i++)  
     {  
       s = StringPrep(s);  
     }  
     return s;  
   }  

LeetCode: 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.

   void reverse(string &s)  
   {  
     int i = 0, j = s.length()-1;  
     while(i<j)  
     {  
       swap(s[i],s[j]);  
       i++;  
       j--;  
     }  
   }  

   string add(string str1, string str2)  
   {  
     string s;  
     int n1 = str1.length(), n2 = str2.length();  
     int i =0, j =0, carry = 0;  
     while(i<n1 && j<n2)  
     {  
       int sum = (str1[i] - '0') + (str2[j] - '0') +carry;  
       s += sum%10 + '0';  
       carry = sum/10;  
       i++; j++;  
     }  
     while(i<n1)  
     {  
       int sum = (str1[i] - '0') +carry;  
       s += sum%10 + '0';  
       carry = sum/10;  
       i++;  
     }  
     while(j<n2)  
     {  
       int sum = (str2[j] - '0') +carry;  
       s += sum%10 + '0';  
       carry = sum/10;  
       j++;  
     }  
     if(carry)  
     {  
       s += carry + '0';  
     }  
     return s;  
   }  

   string multiply(string num1, string num2) {  
     string s, res="0";  
     int n1 = num1.length();  
     int n2 = num2.length();  
     int carry = 0;  
     reverse(num1);  
     reverse(num2);  
     for(int i = 0; i <n2; i++)  
     {  
       carry = 0;  
       s = "";  
       for (int k = 0; k<i; k++)s += '0';  
       for (int j = 0; j <n1; j++)  
       {  
         int m = (num2[i] - '0') * (num1[j] - '0') + carry;  
         s += m%10 + '0';  
         carry = m/10;  
       }  
       while(carry){  
         s += carry%10 + '0';  
         carry = carry/10;  
       }  
       res = add(res,s);  
     }  
     reverse(res);  
     int n = res.length()-1;  
     int i = 0;  
     while(i<n && res[i] == '0')i++;  
     res = res.substr(i);  
     return res;  
   }  

LeetCode: 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.

   int lengthOfLastWord(const char *s) {  
     int i = 0;  
     int cnt = 0;  
     int j = strlen(s) - 1;  
     while(s[j] == ' ')j--;  
     while(i<=j)  
     {  
       if(s[i] == ' ')  
       {  
         cnt = 0;  
       }  
       else  
       {  
         cnt++;  
       }  
       i++;  
     }  
     return cnt;  
   }  

LeetCode: Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

   string addBinary(string a, string b) {  
     int n1 = a.size();  
     int n2 = b.size();  
     if (n1 == 0)return b;  
     if (n2==0)return a;  
     string *imd = new string[n1+n2+2];  
     string res = *imd;  
     int i = n1-1, j = n2-1, k = 0;  
     int carry = 0;  
     while(i>=0 && j>=0)  
     {  
       int x = (a[i--]-48);  
       int y = (b[j--]-48);  
       int sum = x ^ y ^ carry;  
       res += sum+48;k+=2;  
       carry = x&&y || y&&carry || carry&&x;  
     }  
     while(i>=0)  
     {  
       k++;  
       int x = (a[i--]-48);  
       int sum = x ^ carry;  
       res += sum+48;  
       carry = x&&carry;  
     }  
     while(j>=0)  
     {  
       k++;  
       int x = (b[j--]-48);  
       int sum = x ^ carry;  
       res += sum+48;  
       carry = x&&carry;  
     }  
     if(carry)  
     {  
       res += carry+48;  
       k++;  
     }  
     int n;  
     i = 0, j = res.length()-1;  
     while(i<j)  
     {  
       swap(res[i],res[j]);  
       i++;  
       j--;  
     }  
     return res;  
   }  

LeetCode: 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

   typedef vector< vector<int> > vvi;  
   typedef vector<int> vi;  

   int minDistance(string word1, string word2) {  
     int n1 = word1.length();  
     int n2 = word2.length();  
     if(n1 == 0)return n2;  
     if(n2 == 0)return n1;  
     vvi dp(n1+1, vi(n2+1,0));  
     for(int i = 1; i<=n1; i++)dp[i][0] = i;  
     for(int i = 1; i<=n2; i++)dp[0][i] = i;  
     for (int i = 1; i <=n1; i++)  
     {  
       for (int j = 1; j <=n2; j++)  
       {  
         if(word1[i-1] == word2[j-1])  
         {  
           dp[i][j] = dp[i-1][j-1];  
         }  
         else  
         {  
           dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;  
         }  
       }  
     }  
     return dp[n1][n2];  
   }  

LeetCode: Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

   bool alphanum(char s)  
   {  
     if (s>='0' && s<='9')return true;  
     if (s>='a' && s<='z')return true;  
     if (s>='A' && s<='Z')return true;  
     return false;  
   }  



   bool isPalindrome(string s) {  
     int i = 0, j = s.length()-1;  
     if(j<1)return true;  
     while(i<j)  
     {  
       if(s[i]>='A' && s[i]<='Z')s[i] += 32;  
       if(s[j]>='A' && s[j]<='Z')s[j] += 32;  
       if(!alphanum(s[i])){  
         i++;  
         continue;  
       }  
       else if(!alphanum(s[j]))  
       {  
         j--;  
         continue;  
       }  
       if(s[i] != s[j])return false;  
       i++;  
       j--;  
     }  
     return true;  
   }  

LeetCode: Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. 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.

   struct node
   {
     int cost;
     string s;
   };

   struct mycompare{
     bool operator()(node &a, node &b) const
     {
        return (a.cost > b.cost);
     }
   };
   #define INT_MAX 0x7FFFFFFF

   bool canTrans(string a, string b){  
     int dif = 0;  
     for (int i = 0; i < a.length(); i++){  
       if (a[i] != b[i]){  
         dif++;  
         if (dif >= 2){  
           return false;  
         }  
       }  
     }  
     return true;  
   }



   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     queue<string> wq;  
     queue<int> lq;  
     wq.push(start);  
     lq.push(1);  
     while (!wq.empty()){  
       string word(wq.front());  
       wq.pop();  
       int lev = lq.front();  
       lq.pop();  
       for (int i = 0; i < word.length(); i++){  
         char temp = word[i];  
         for (char c = 'a'; c <= 'z'; c++){  
           word[i] = c;  
           if (word == end){  
             return lev + 1;  
           }  
           if (dict.find(word) != dict.end()){  
             wq.push(word);  
             lq.push(lev + 1);  
             dict.erase(word);  
           }  
           word[i] = temp;  
         }  
       }  
     }  
     return 0;  
   }  

LeetCode: 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".

   bool wordBreak(string s, unordered_set<string> &dict) {  
     int l = s.length();  
     vector< vector<int> > m (l, vector<int>(l,0));  
     for (int i = 0; i <l; i++)  
     {  
       for (int j = i; j < l; j++)  
       {  
         if (dict.find(s.substr(i,j-i+1)) != dict.end())m[i][j] = 1;  
       }  
     }  
     for (int k = 2; k<=l ; k++)  
     {  
       for(int i = 0; i+k-1 < l ; i++)  
       {  
         int j = i+k-1;  
         for (int p = i; p <j; p++)  
         {  
           if(m[i][p] && m[p+1][j]){m[i][j] = true; break;}  
         }  
       }  
     }  
     return m[0][l-1];  
   }