LeetCode: Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
   typedef vector<vector<bool> > vvb;  
   typedef vector<vector<char> > vvc;  
   
   bool backtrack(vvc &board, string &word, int i, int j, int x, int n, int row, int col, vvb &visited)  
   {  
     if(x == n && word[x] == board[i][j])return true;  
     if (word[x] != board[i][j]) return false;  
       
     bool left = false, right = false, up = false, down = false;  
     visited[i][j] = true;  
     if (j > 0 && visited[i][j-1] == false){  
       left = backtrack(board, word, i, j-1, x+1, n, row, col, visited);  
       if (left) return true;  
     }  
   
     if (j < col && visited[i][j+1] == false){  
       right = backtrack(board, word, i, j+1, x+1, n, row, col, visited);  
       if (right) return true;  
     }  
   
     if (i > 0 && visited[i-1][j] == false){  
       up = backtrack(board, word, i-1, j, x+1, n, row, col, visited);  
       if (up) return true;  
     }  
       
     if (i < row && visited[i+1][j] == false){  
       down = backtrack(board, word, i+1, j, x+1, n, row, col, visited);  
       if (down) return true;  
     }  
     visited[i][j] = false;  
     return false;  
   }  
   
   bool exist(vector<vector<char> > &board, string word) {  
     int n = word.length();  
     if(!n)return false;  
     int row = board.size();  
     if(!row) return false;  
     int col = board[0].size();  
     if(row*col < n)return false;  
   
     vvb visited(row, vector<bool>(col, false));   
     for (int i = 0; i < row; i++)  
     {  
       for(int j = 0; j < col; j++)  
       {  
         if(board[i][j] == word[0] && backtrack(board, word, i , j, 0,n-1, row-1, col-1, visited))return true;  
       }  
     }  
     return false;  
   } 

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: Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

 /**  
  * Definition for an interval.  
  * struct Interval {  
  *   int start;  
  *   int end;  
  *   Interval() : start(0), end(0) {}  
  *   Interval(int s, int e) : start(s), end(e) {}  
  * };  
  */  
   
   static bool compare(Interval x, Interval y)  
   {  
     return (x.start < y.start);  
   }  
   
   vector<Interval> merge(vector<Interval> &intervals) {  
     sort(intervals.begin(), intervals.end(), compare);  
   
     int n = intervals.size();  
     vector<Interval> res;  
   
     for (int i = 0; i< n; i++)  
     {  
       int j = i;  
       int greatest = intervals[i].end;  
       while (j<n-1 && intervals[j+1].start <= greatest){  
         j++;  
         if(intervals[j].end > greatest)greatest = intervals[j].end;  
       }  
       if(j == i)  
       {  
         res.push_back(intervals[i]);  
       }  
       else  
       {  
         Interval x(intervals[i].start, greatest);  
         res.push_back(x);  
         i = j;  
       }  
     }  
     return res;  
   }  

LeetCode: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

   int divide(int dividend, int divisor) {  
     long long x = abs((long long)divisor);  
     long long y = abs((long long)dividend);  
     long long res = 0, sum = x, negative = 0 , q = 1;  
   
     if (divisor < 0 && dividend < 0)negative = 0;  
     else if (divisor < 0 || dividend < 0)negative = 1;  
   
     if(x>y)return 0;  //y/x  
   
     while(sum)  
     {  
       if (sum << 1 <= y)  
       {  
         sum = sum<<1;  
         q = q<<1;  
       }  
       else  
       {  
         res += q;  
         if(y - sum < x) sum = 0;  
         else {  
           y = y - sum;  
           sum = x;  
           q = 1;  
         }  
       }  
     }  
     if(negative)  
       res = -res;  
   
     return (int)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: Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *removeNthFromEnd(ListNode *head, int n) {  
     ln *dummy = new ln(0);  
     dummy->next = head;  
     ln *fast = dummy, *slow = dummy;  
     while(n--)  
     {  
       fast = fast->next;  
     }  
       
     while(fast->next)  
     {  
       fast = fast->next;  
       slow = slow->next;  
     }  
       
     slow->next = slow->next->next;  
       
     return dummy->next;  
   }  

LeetCode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *partition(ListNode *head, int x) {  
     ln *list1 = new ln(0);  
     ln *list2 = new ln(0);  
       
     ln *tmp = head, *newHead = NULL, *list2head = list2;  
     while(tmp)  
     {  
       if (tmp->val < x)  
       {  
         list1->next = tmp;  
         list1 = tmp;  
         if(!newHead) newHead = tmp;  
       }  
       else  
       {  
         list2->next = tmp;  
         list2 = tmp;  
       }  
       tmp = tmp->next;  
     }  
     if(!newHead) newHead = list2head->next;  
     list1->next = list2head->next;  
     list2->next = NULL;  
   
     return newHead;  
   }  

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: Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

   int maxProfit(vector<int> &prices) {  
     int n = prices.size();  
     if(n == 0)return 0;  
     vector<int> smallest(n, 0);  
     smallest[0] = INT_MAX;  
     int min = prices[0], profit = 0;  
       
     for (int i = 1; i <n; i++)  
     {  
       int t = prices[i];  
       smallest[i] = min;  
       if(prices[i] < min) min = prices[i];  
     }  
       
     for(int i = 1; i < n; i++)  
     {  
       int diff = prices[i] - smallest[i];   
       if(profit < diff) profit = diff;  
     }  
       
     return profit;  
   }  

LeetCode: Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

   typedef pair<int, int> ii;  
   
   bool compare(ii a, ii b)  
   {  
     return (a.second < b.second);  
   }  
   
   vector<int> twoSum(vector<int> &numbers, int target) {  
     int l = numbers.size();  
     vector < ii > num(l);  
     for(int i = 0;i<l; i++)  
     {  
       num[i].first = i;  
       num[i].second = numbers[i];  
     }  
       
     sort(num.begin(),num.end(),compare);  
     vector <int> v;  
     int i = 0, j = numbers.size()-1;  
     while(i<j)  
     {  
       int sum = num[i].second+num[j].second;  
       if(sum == target)  
       {  
         int small,big;  
         small = min(num[i].first, num[j].first);  
         big = max(num[i].first, num[j].first);  
         v.push_back(small+1);  
         v.push_back(big+1);  
         break;  
       }  
       else if(sum < target)i++;  
       else j--;  
     }  
     return v;  
   }  

LeetCode: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
   typedef ListNode ln;  
   
   int count(ln *head)  
   {  
     int cnt = 0;  
     while(head){  
       head = head->next;  
       cnt++;  
     }  
     return cnt;  
   }  
   
   ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
     if(l1 == NULL && l2 == NULL)return NULL;  
     if(l1 == NULL)return l2;  
     if(l2 == NULL)return l1;  
   
     ln *head = NULL,*last;  
     int sum = 0, carry = 0;  
   
     while(l1 && l2)  
     {  
       sum = l1->val + l2->val + carry;  
       carry = sum/10;  
       sum = sum%10;  
       ln *n = new ln(sum);  
       if(!head){head = n; last = head;}  
       else  
       {  
         last->next = n;  
         last = n;  
       }  
   
       l1 = l1->next;  
       l2 = l2->next;  
     }  
   
     while(l1)  
     {  
       sum = l1->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l1 = l1->next;  
       last = last->next;  
     }  
   
     while(l2)  
     {  
       sum = l2->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l2 = l2->next;  
       last = last->next;  
     }  
   
     if (carry)last->next = new ln(carry);  
   
     return head;  
   }  

LeetCode: Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

   int reverse(int x) {  
     int sign = 1, res = 0;  
     if (x<0)sign = -1;  
     vector< int > v;  
     x=abs(x);  
   
     while(x)  
     {  
       v.push_back(x%10);  
       x = x/10;  
     }  
   
     for(decltype(v.begin()) it = v.begin(); it != v.end(); it++)  
     {  
       res = res*10 + (*it);  
     }  
   
     return (res*sign);  
   }  

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: Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

   bool isPalindrome(int x) {  
     int d = 0;  
     int n = x;  
     if(x<0)return false;  
     while(n)  
     {  
       d++;  
       n=n/10;  
     }  
     int i = d-1, j = 0;  
     while(i>j)  
     {  
       int pi = pow(10,i), pj = pow(10,j), pk = pow(10,j+1);  
       if(x/pi != (x%pk)/pj)return false;  
       x = x%pi;  
       i--;j++;  
     }  
     return true;  
   }  

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: 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

   typedef vector<vector<int> > vvi;  
   typedef vector<int> vi;  
   
   #define tr(v, i) for(decltype((v).begin()) (i) = (v).begin(); (i) != (v).end(); (i)++)  
   
   vector<vector<int> > threeSum(vector<int> &num) {  
     set< vector<int> > S;  
     vvi V;  
   
     sort(num.begin(),num.end());  
   
     int n = num.size();  
   
     int i, j,k,sum;  
     for (k = 0; k<n-2; k++)  
     {  
       i = k+1; j = n-1;  
       while(j > i)  
       {  
         sum = num[i]+num[j]+num[k];  
         if(sum == 0)  
         {  
           vi v;  
           v.push_back(num[k]);  
           v.push_back(num[i]);  
           v.push_back(num[j]);  
           S.insert(v);  
           i++;  
           j--;  
         }  
         else if (sum > 0)  
         {  
           j--;  
         }  
         else i++;  
       }  
     }  
   
     tr (S,it)  
     {  
       V.push_back(*it);  
     }  
   
     return V;  
   
   }  

LeetCode: 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

   typedef vector< vector<int> > vvi;  
   typedef vector< int > vi;  
   
   #define tr(v, it) for(decltype((v).begin()) (it) = (v).begin(); (it) != (v).end(); (it)++)   
   
   vector<vector<int> > fourSum(vector<int> &num, int target) {  
     set < vector<int> > S;  
     vvi V;  
     sort(num.begin(),num.end());  
       
     int n = num.size();  
       
     for (int i = 0; i < n-3; i++)  
     {  
       for (int j = i+1; j <n-2; j++)  
       {  
         int k = j+1, l = n-1;  
         while(k<l)  
         {  
           int sum = num[i]+num[j]+num[k]+num[l];  
           if(sum == target)  
           {  
             vi v;  
             v.push_back(num[i]);  
             v.push_back(num[j]);  
             v.push_back(num[k]);  
             v.push_back(num[l]);  
             S.insert(v);  
             k++;  
             l--;  
           }  
           else if (sum<target)k++;  
           else l--;  
         }  
       }  
     }  
     tr(S,it)  
     {  
       V.push_back(*it);  
     }  
     return V;  
   }  

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;  
   }