Palindrome Linked List #LeetCode

Problem Reference:
https://leetcode.com/problems/palindrome-linked-list/

Problem Statement:
Given a singly linked list, determine if it is a palindrome.
Follow up: Could you do it in O(n) time and O(1) space?

Solution:
Reverse the second half. And compare two halves.

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if (!head || !head->next) { return true; } ListNode* slow = head; ListNode* fast = head; // find center while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } // cut in the middle ListNode* secondHalf = slow->next; slow->next = NULL; // reverse second half ListNode* p = secondHalf; ListNode* reversedSecondHalf = NULL; while(p) { ListNode * current = p; p = p->next; current->next = reversedSecondHalf; reversedSecondHalf = current; } // compare two halves. // The middle node is present when n = 2k + 1. // It will be in the second half and will be skipped because of the condition (list1 && list2) ListNode* list1 = head; ListNode* list2 = reversedSecondHalf; while(list1 && list2) { if (list1->val != list2->val) { return false; } list1 = list1->next; list2 = list2->next; } return true; } };

Lowest Common Ancestor of a Binary Search Tree #LeetCode

Problem Reference:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Problem Statement:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Solution:

Binary tree traversal.

Termination case :
1). find LCA in left subtree
2). find LCA in right subtree
3). find LCA at current Node, (left + current, right + current, left + right)

Declare a struct Result to log searching result
struct Result {
  bool isPFind;
  bool isQFind;
}
or use a integer where bit is used to indicate whether node is found or not.

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { result = NULL; find(root, p, q); return result; } unsigned find(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root) { return 0; } unsigned left = find(root->left, p, q); unsigned current = 0 | (root == p ? 1 : 0 ) | (root == q ? 2 : 0); unsigned right = find(root->right, p, q); if (left == 3) { return 3; } else if (right == 3) { return 3; } else if ((left | current | right) == 3) { result = root; return 3; } return left | current | right; } TreeNode* result; };

Delete Node in a Linked List #LeetCode

Problem Reference:
https://leetcode.com/problems/delete-node-in-a-linked-list/

Problem Statement:
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution:

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void deleteNode(ListNode* node) { ListNode* next = node->next; node->val = next->val; node->next = next->next; } };

Valid Anagram #LeetCode

Question Reference:
https://leetcode.com/problems/valid-anagram/

Question Statement:

Given two strings s and t, write a function to determine if t is an anagram of s.
For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.
Note: You may assume the string contains only lowercase alphabets.

Solution:


Solution 1:
Get statistics map for each string and compare these two maps.

class Solution { public: bool isAnagram(string s, string t) { std::unordered_map stats1 = getStats(s); std::unordered_map stats2 = getStats(t); if (stats1.size() != stats2.size()) { return false; } for (auto iter = stats1.begin(); iter != stats2.end(); iter++) { if (stats2.find(iter->first) == stats2.end() || stats2[iter->first] != iter->second) { return false; } } return true; } std::unordered_map getStats(string s) { std::unordered_map stats; for (char c : s) { if (stats.find(c) == stats.end()) { stats[c] = 1; } else { stats[c]++; } } return stats; } };

Solution2:
Use an array to store statistics information.

class Solution { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) { return false; } vector stats(256, 0); for (char c : s) { stats[c]++; } for (char c : t) { stats[c]--; } for (int i = 0; i < 256; i++) { if (stats[i] != 0) { return false; } } return true; } };

Pascal's Triangle #LeetCode

Problem Reference:
https://leetcode.com/problems/pascals-triangle/

Problem Statement:

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;

        for (int i = 0; i <= numRows - 1; i++) {
            vector<int> current(i+1, 1);
            for (int j = 1; j < i; j++) {
                current[j] = result[i-1][j-1] + result[i-1][j];
            }
            result.push_back(current);
        }

        return result;
    }
};

Sliding Window Maximum #LeetCode

https://leetcode.com/problems/sliding-window-maximum/

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Solution 1:

For each window, get maximum using a simple 1 by 1 comparison. O(k)
Total time complexity O(k) * N = O(kN).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: // quick solution vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; int size = nums.size(); if (size == 0) return result; for (int i = 0; i <= size - k; i++) { result.push_back(max(nums, i, i + k - 1)); } return result; } int max(vector<int>& nums, int start, int end) { int max = nums[start]; for (int i = start + 1; i <= end; i++) { if (nums[i] > max) max = nums[i]; } return max; } };

Solution 2:

Using a heap, for each window, remove 1 instance of the beginning element of previous window, and add 1 ending element or current window.
For each window, get maximum using 2 * O(log k)
Total time complexity 2 * O(log k) * N = O(logk * N).

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

class Solution { public: // quick solution std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) { std::vector<int> result; int size = nums.size(); if (size == 0) return result; // created an ordered std::map for numbers within window std::map<int, int> window; for (int i = 0; i < k; i++) { insertToMap(window, nums[i]); } result.push_back(window.rbegin()->first); int p = 0; while(p < size && p + k < size) { // update window popOffMap(window, nums[p]); insertToMap(window, nums[p+k]); // get the maximum within window result.push_back(window.rbegin()->first); p++; } return result; } void insertToMap(std::map<int, int>& map, int val) { if (map.find(val) != map.end()) map[val] = map[val] + 1; else map[val] = 1; } void popOffMap(std::map<int, int>& map, int val) { if (map[val] == 1) map.erase(val); else map[val] = map[val] - 1; } };

[LeetCode] Maximal Rectangle

Link : http://oj.leetcode.com/problems/maximal-rectangle/

More information:
http://dp2.me/blog/?p=482

Thanks for your help. --> 无齿的兔子, 鹿杖客

 
#include <iostream>
#include <vector>

class Solution {
    public:
    int maximalRectangle(std::vector<std::vector<char> > &matrix) {
        int n = matrix.size();
        if(n==0) return 0;
        int m = matrix[0].size();
        if(m==0) return 0;
        std::vector<int> height(m, 0);
        std::vector<int> left(m, 0);
        std::vector<int> right(m, 0);
        int maxArea = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                height[j] = (matrix[i][j]=='1')? height[j]+1 : 0;
                left[j] = j;
                while(left[j]>0 && height[left[j]-1]>=height[j])
                left[j] = left[left[j]-1];
            }
            for(int j=m-1; j>=0; j--)
            {
                right[j] = j;
                while(right[j]<m-1 && height[j]<=height[right[j]+1])
                right[j] = right[right[j]+1];
            }
            for(int j=0; j<m; j++)
            maxArea = std::max(maxArea, (right[j]-left[j]+1)*height[j]);
        }
        return maxArea;
    }
};

[LeetCode] Classification

Sorting is enabled. Please click on the title to sort by specific column

Problem	Classification	Method
Evaluate Reverse Polish Notation	Math	Stack
Max Points on a Line	Count	Map
Sort List	List, BST, Graph	Merge Sort
LRU Cache	Design	Map, List
Binary Tree Postorder Traversal	List, BST, Graph	Stack
Binary Tree Preorder Traversal	List, BST, Graph	Stack
Reorder List	List, BST, Graph	Divide
Linked List Cycle II	List, BST, Graph	Two Pointers
Linked List Cycle	List, BST, Graph	Two Pointers
Word Break II	List, BST, Graph	DP
Word Break	List, BST, Graph	DP
Copy List with Random Pointer	List, BST, Graph	MAP, Copy&Break
Single Number II	Math	Bit
Single Number	Math	Bit
Candy	Math	Stack
Gas Station	Math	DP
Clone Graph	List, BST, Graph	Map
Palindrome Partitioning II	String	DP
Palindrome Partitioning	String	DP
Surrounded Regions	List, BST, Graph	BST
Sum Root to Leaf Numbers	List, BST, Graph	DSF
Longest Consecutive Sequence	Math	Set
Word Ladder II	List, BST, Graph	BST
Word Ladder	List, BST, Graph	BST
Valid Palindrome	String	Two Pointers
Binary Tree Maximum Path Sum	List, BST, Graph	DFS
Best Time to Buy and Sell Stock III	Array	Stack, DP
Best Time to Buy and Sell Stock II	Array
Best Time to Buy and Sell Stock	Array
Triangle	Math	DP
Pascal's Triangle II	Math	DP
Pascal's Triangle	Math	DP
Populating Next Right Pointers in Each Node II	List, BST, Graph	Two Pointers
Populating Next Right Pointers in Each Node	List, BST, Graph	Two Pointers
Distinct Subsequences	String	DP
Flatten Binary Tree to Linked List	List, BST, Graph	DFS, Wrapper
Path Sum II	List, BST, Graph	DFS
Path Sum	List, BST, Graph	DFS
Minimum Depth of Binary Tree	List, BST, Graph	DFS
Balanced Binary Tree	List, BST, Graph	DFS
Convert Sorted List to Binary Search Tree	List, BST, Graph	Divide and Conquer
Convert Sorted Array to Binary Search Tree	List, BST, Graph	Divide and Conquer
Binary Tree Level Order Traversal II	List, BST, Graph	List
Construct Binary Tree from Inorder and Postorder Traversal	List, BST, Graph	Divide and Conquer
Construct Binary Tree from Preorder and Inorder Traversal	List, BST, Graph	Divide and Conquer
Maximum Depth of Binary Tree	List, BST, Graph	DFS
Binary Tree Zigzag Level Order Traversal	List, BST, Graph	BSF, List
Binary Tree Level Order Traversal	List, BST, Graph	BSF, List
Symmetric Tree	List, BST, Graph	DFS, Divide & Conquer
Same Tree	List, BST, Graph	DFS, Divide & Conquer
Recover Binary Search Tree	List, BST, Graph	DFS, In-Order, Store
Recover Binary Search Tree	List, BST, Graph	DFS, In-Order, Store
Validate Binary Search Tree	List, BST, Graph	DFS, In-Order, Store
Interleaving String	String	DP
Unique Binary Search Trees II	String	DP
Unique Binary Search Trees	String	DFS, Divide & Conquer
Binary Tree Inorder Traversal	String	DFS, Divide & Conquer
Restore IP Addresses	String	DFS
Reverse Linked List II	List, BST, Graph	Two Pointers
Subsets II	List, BST, Graph	DFS
Decode Ways	String, List, BST, Graph	DFS
Gray Code	Math, String, List, BST, Graph	DFS, Math
Merge Sorted Array	Sort	Merge Sort
Scramble String	String, List, BST, Graph	DFS
Partition List	List, BST, Graph	Two Pointers
Maximal Rectangle	List, BST, Graph	DP
Largest Rectangle in Histogram	List, BST, Graph	DP
Remove Duplicates from Sorted List II	List, BST, Graph	Two Pointers
Remove Duplicates from Sorted List	List, BST, Graph	Two Pointers
Search in Rotated Sorted Array II	List, BST, Graph	Divided & Conquer, Binary Search
Remove Duplicates from Sorted Array II	List, BST, Graph	Two Pointers
Word Search	List, BST, Graph	DFS
Subsets	List, BST, Graph	DFS
Combinations	List, BST, Graph	DFS
Minimum Window Substring	String, List, BST, Graph	Count
Sort Colors	Sort, List, BST, Graph	Two Pointers
Search a 2D Matrix	List, BST, Graph	Binary Search, Transformation
Set Matrix Zeroes	other	other
Edit Distance	String, List, BST, Graph	DP
Simplify Path	String, List, BST, Graph	DP, Stack
Climbing Stairs	List, BST, Graph	DP
Sqrt(x)	Math	Binary Search, Bit Manipulation
Text Justification	String	Other
Plus One	Math	Other
Valid Number	String	Other
Merge Two Sorted Lists	List, BST, Graph	Merge Sort
Minimum Path Sum	List, BST, Graph	DFS
Unique Paths II	List, BST, Graph	DP
Unique Paths	List, BST, Graph	DP
Rotate List	List, BST, Graph	Two Pointers
Permutation Sequence	Math	Bit Manipulation
Spiral Matrix II	Other	Other
Length of Last Word	String	Other
Insert Interval	Other	Other
Merge Intervals	Other	Other
Jump Game	List, BST, Graph	DP
Spiral Matrix	Other	Other
Maximum Subarray	List, BST, Graph	DP
N-Queens II	List, BST, Graph	DFS
N-Queens	List, BST, Graph	DFS
Pow(x, n)	Math	Bit Manipulation
Anagrams	String	Count
Rotate Image	Other	Other
Permutations II	Math	Other
Permutations	Math	Other
Jump Game II	List, BST, Graph	DP
Wildcard Matching	String, Pattern	Greedy
Multiply Strings	Math	Other
Trapping Rain Water	Math	DP
First Missing Positive	Math	Two Pointers
Combination Sum II	Math	DP
Combination Sum	Math	DP
Count and Say	String	DP
Sudoku Solver	List, BST, Graph	Other
Valid Sudoku	List, BST, Graph	DFS
Search Insert Position	List, BST, Graph	Binary Search
Search for a Range	List, BST, Graph	Binary Search
Search in Rotated Sorted Array	List, BST, Graph	Binary Search
Longest Valid Parentheses	String, List, BST, Graph	DP
Next Permutation	Math	Other
Substring with Concatenation of All Words	String, List, BST, Graph	DFS
Divide Two Integers	Math	Bit Manipulation
Implement strStr()	String, Pattern	Brute Force, KMP
Remove Element	List, BST, Graph	Two Pointers
Remove Duplicates from Sorted Array	List, BST, Graph	Two Pointers
Reverse Nodes in k-Group	List, BST, Graph	Two Pointers
Swap Nodes in Pairs	List, BST, Graph	Two Pointers
Merge k Sorted Lists	List, BST, Graph	Heap, Compare
Generate Parentheses	String, List, BST, Graph	DP
Valid Parentheses	String, List, BST, Graph	Stack
Remove Nth Node From End of List	List, BST, Graph	Two Pointers
Letter Combinations of a Phone Number	String, List, BST, Graph	DFS, Backtrace
Letter Combinations of a Phone Number	String, List, BST, Graph	DFS, Backtrace
4 Sum	Math, Combination	Two Pointers
3 Sum Closest	Math, Combination	Two Pointers
3 Sum	Math, Combination	Two Pointers
Longest Common Prefix	String, List, BST, Graph
Roman to Integer	String	Other, Pattern
Integer to Roman	String	Other, Pattern
Container With Most Water	List, BST, Graph	Two Pointers, Other
Regular Expression Matching	String, List, BST, Graph	DFS, Greedy
Palindrome Number	String, List, BST, Graph	Two Pointers
String to Integer (atoi)	String	Other
Reverse Integer	Math	Overflow
ZigZag Conversion	Other	Other
Longest Palindromic Substring	String	DP, Manacher's Algorithm
Add Two Numbers	Other	Other
Longest Substring Without Repeating Characters	String	Two Pointers
Median of Two Sorted Arrays	Math	Divide & Conquer
2 Sum	Math	Two Pointers

[LeetCode] LRU Cache

 
class LRUCache{
    public:
    typedef std::pair<int, int> ENTRY;
    LRUCache(int capacity) {
        max = capacity;
        count = 0;
    }
    
    int get(int key) {
        if(map.find(key)==map.end())
        return -1;
        else
        {
            entry.splice(entry.begin(), entry, map[key]);
            return (map[key])->second;
        }
    }
    
    void set(int key, int value) {
        if(map.find(key)==map.end())
        {
            entry.push_front(ENTRY(key, value));
            map[key] = entry.begin();
            if(++count>max)
            {
                int tmp = entry.back().first;
                entry.erase(--entry.end());
                count--;
                map.erase(tmp);
            }
        }
        else
        {
            entry.splice(entry.begin(), entry, map[key]);
            map[key]->second = value;
        }
    }
    
    int count;
    int max;
    std::list<std::pair<int, int>> entry;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
};

[LeetCode] Reorder List

Link : http://oj.leetcode.com/problems/reorder-list/

Analysis :
Two pointers, head and tail

head pointer : scans from the start
tail pointer  : first dig into the list until and last one. From there tail behaves as the node pointer pointing to the last node

head and tail scan from two ends and modify the link list as expected.
Be careful of the stop case.

 
/**
* Definition for singly-linked list.
* struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    void reorderList(ListNode *head) {
        if(head==NULL)
            return;
        int n=0;
        ListNode dummy(0);
        dummy.next = head;
        ListNode * cursor = &dummy;
        reorder(cursor, cursor);
    }
    
    bool reorder(ListNode*& head, ListNode* tail)
    {
        // base case
        if(tail->next==NULL)
            return true;
        // tail point to second to last node
        
        // stop case
        if(!reorder(head, tail->next)||head==tail||head->next==tail);
            return false;
        ListNode* tmp = tail->next;
        tail->next=NULL;
        
        tmp->next = head->next;
        head->next = tmp;
        
        head = head->next->next;
        return true;
    }
};

[LeetCode] Sort List

Link : http://oj.leetcode.com/problems/sort-list/
Sort a linked list in O(n log n) time using constant space complexity.

iterative version of merge sort.
Code is ugly and needs substantial modification.

class Solution {
    public:
    
    ListNode *sortList(ListNode *head) {
        if(!head) return NULL;
        ListNode dummy(0);
        dummy.next = head;
        // get length
        int n=0;
        ListNode* cursor=&dummy;
        ListNode* tmp;
        while(cursor->next) { n++; cursor=cursor->next; }
        
        ListNode* current_first=head;
        ListNode* next_first=NULL;
        
        ListNode* merge_head=NULL;
        ListNode* merge_tail=NULL;
        
        // scan using different step
        for(int step=1; step<n; step*=2)
        {
            // initialization
            cursor = &dummy;
            current_first = dummy.next;
            // for each step, merge two adjacent sub lists
            for(int i=0; i<n; i+=step*2)
            {
                next_first = moveNode(current_first, step*2-1);
                if(next_first) // cut link between different sub list
                {
                    tmp = next_first->next;
                    next_first->next = NULL;
                    next_first = tmp;
                }
                merge(current_first, step, merge_head, merge_tail);
                cursor->next = merge_head; // concatenation
                cursor = merge_tail; // ready for next concatenation
                current_first = next_first; // ready for next merge
            }
        }
        return dummy.next;
    }
    
    ListNode* moveNode(ListNode* p, int step)
    {
        while(step-->0&&p) p=p->next;
        return p;
    }
    
    void merge(ListNode* head, int step, ListNode*& merge_head, ListNode*& merge_tail)
    {
        if(head==NULL) return;
        ListNode dummy(0);
        ListNode* tmp;
        
        ListNode* cursor = &dummy;
        ListNode* l1 = head;
        // get second sub-list
        ListNode* l2 = head;
        // get the node pointing to the head of second sub-list
        l2 = moveNode(l2, step-1);
        if(l2) // cut link between different sub list
        {
            tmp = l2->next;
            l2->next = NULL;
            l2 = tmp;
        }
        
        while(l1||l2)
        {
            if((l1&&!l2)||(l1&&l2&& l1->val <= l2->val))
            {
                tmp = l1->next;
                l1->next=NULL;
                cursor->next = l1;
                
                l1=tmp;
                cursor=cursor->next;
            }
            else
            {
                tmp = l2->next;
                l2->next=NULL;
                cursor->next = l2;
                
                l2=tmp;
                cursor=cursor->next;
            }
        }
        merge_head = dummy.next;
        merge_tail = cursor;
    }
    
};

[LeetCode] Binary Tree Preorder Traversal

Link : http://oj.leetcode.com/problems/binary-tree-preorder-traversal/

/**
* Definition for binary tree
* struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };


class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(root==NULL)
            return ret;
        std::stack<TreeNode*> ss;
        ss.push(root);
        TreeNode* node;
        while(ss.size()>0)
        {
            node = ss.top();
            ss.pop();
            ret.push_back(node->val);
            if(node->right)
                ss.push(node->right);
            if(node->left)
                ss.push(node->left);
            
        }
        return ret;
    }
};

[LeetCode] Binary Tree Postorder Traversal

Link : http://oj.leetcode.com/problems/binary-tree-postorder-traversal/

/**
* Definition for binary tree
* struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
    public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(root==NULL)
            return ret;
        TreeNode* current;
        stack<TreeNode*> s;
        s.push(root);
        while(s.size()>0)
        {
            current = s.top();
            s.pop();
            if(current==NULL)
            {
                current = s.top();
                s.pop();
                ret.push_back(current->val);
                continue;
            }
            s.push(current);
            s.push(NULL);
            if(current->right)
                s.push(current->right);
            if(current->left)
                s.push(current->left);
        }
        return ret;
    }
};

[LeetCode] Word Break

Problem

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

First scan, mark every possible string section.

Second scan, dynamic programming,  for every string 0~i, it is a valid break-able string only if its previous string 0~j and new part j+1~ i are both valid words in the dictionary.

 


class Solution {  
 public:  
      bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {  
           int n = s.size();  
           if(n==0||dict.size()==0)  
                return false;  
           std::vector<std::vector<bool>> map(n+1, std::vector<bool>(n+1, false));  
           map[0][0] = true;  
           std::vector<bool> memo(n+1, false);  
           memo[0] = true;  
           std::string tmp;  
           for(int i=0; i<n; i++)  
           {  
                for(int j=i; j<n; j++)  
                {  
                     tmp = s.substr(i, j-i+1);  
                     if(dict.find(tmp)!=dict.end())  
                          map[i+1][j+1]=true;  
                }  
           }  
           for(int i=0; i<n; i++)  
           {  
                for(int j=0; j<=i; j++)  
                {  
                     if(memo[j+1-1]&&map[j+1][i+1])  
                          memo[i+1] = true;  
                }  
           }  
           return memo[n];  
      }  
 };  

[LeetCode] ZigZag Conversion

 
class Solution {
    public:
    string convert(string s, int nRows) {
        int n=s.size();
        if(n==0) return "";
        if(nRows==1)
        return s;
        int half = nRows-1;
        int step = half*2;
        string ret="";
        
        vector<string> v(nRows,"");
        
        for(int i=0; i<n; i+=step)
        {
            for(int j=0; j<half; j++)
            if(i+j<n) v[j]+=s[i+j];
            for(int j=0; j<half; j++)
            if(i+half+j<n) v[half-j]+=s[i+half+j];
        }
        for(int i=0; i<nRows; i++)
        ret+=v[i];
        return ret;
    }
};

[LeetCode] Validate Binary Search Tree

Link : Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

[LeetCode] Merge Sorted Array

Link : Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

[LeetCode] Valid Number

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

Analysis:
Test case is quite important.
To make clear what if input is NULL, '\0', or "    "(only space).
exponential part is quite important.

I tried several times, and there is always some case that I didn't expect.
This is intentionally a vague problem. So ask for details from interviewers, if possible.

[LeetCode] Merge Two Sorted List

Problem : Merge Two Sorted List

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analysis:
Not a difficult problem. But make clear whether we need a new (created) list, or just the merged one.
A dummy node at first will be very helpful and no need to worry about how to get the pointer to the first node.

[LeetCode] Valid Parentheses

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.

Analysis:
To find whether parentheses are paired correctly, a stack would be useful.
Scan from the start of string to its end.
When meeting '(','[','{', push them to stack.
When ')', ']', '}' is scanned, find its paired parentheses in the stack.
1) if the stack is empty, return false
2) if the top element in the stack cannot match, i.e. not paired in '(' with ')', '[' with ']' and '{' with '}', return false.
In the end, if the stack is empty, i.e. all parentheses are paired, return true. Other wise return false.