Restore IP Addresses

Restore IP AddressesAug 8 '12

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

This one is actually more tricky than it seems to be as it involves several corner cases.
DFS

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() > 12 || s.size() < 4) return vector<string>();
        return getValidIP(s.c_str(), 0);
    }
    
    vector<string> getValidIP(const char *c, int n) {
        const char *head = c;
        if (n == 3) {
            int num = 0;
            while (*c != '\0') {
                num = num * 10 + *c - '0';
                ++c;
            }
            vector<string> ret;
            
            // last segment requirements
            // at least one digit and at most one leading zero
            if (c - head > 1 && *head == '0' || c == head) return ret;
            
            // segment number cannot exceed 255
            if (num <= 255) {
                string seg(head, c - head);
                ret.push_back(seg);
            }
            return ret;
        }
        int num = 0;
        vector<string> ret;
        for (int i = 0; i < 3; ++i) {
            // reaches end or digits exceed 3
            if (*c == '\0' || c - head > 2) break;
            
            num = num * 10 + *c - '0';
            
            // each segment can be at most 255
            if (num > 255) break;
            
            vector<string> rest = getValidIP(++c, n + 1);
            string add_seg(head, c - head);
            for (auto s : rest) {
                string address(add_seg);
                address += ".";
                address += s;
                ret.push_back(address);
            }
            
            // only one leading 0 allowed
            if (*(c - 1) == '0' && i == 0) break;
        }
        return ret;
    }
};

Reverse Linked List II

Reverse Linked List IIJun 27 '12

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

This looks fairly easy but actually it's pretty tricky. Each recursion takes the node to be processed and returns itself so that the upper level can change the 'next' pointer backwards as stack pops. The special case is that during the backward process, when m == 0 we reach the first node in the region to be reversed (let's call it 'region'). At that time the node before it should get the next node after the 'region'. That's where the nodeAfterN is used. Also the node before m == 0 should get the original last node in the 'region', which now becomes the head node in the 'region'. This is achieved by returning the pointer of that last node to the upper level of recursion, AKA nodeAtN.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        nodeAtN = NULL;
        nodeAfterN = NULL;
        return revHelper(head, m - 1, n - 1);
    }
    
    ListNode *revHelper(ListNode *current, int m, int n) {
        if (!current) return NULL;
        ListNode *ret = current;
        if (m > 0) {
            current->next = revHelper(current->next, m - 1, n - 1);
        }
        else if (n > 0) {
            ListNode *currentNext = revHelper(current->next, m - 1, n - 1);            
            currentNext->next = current;
            if (m == 0) {
                current->next = nodeAfterN;
                ret = nodeAtN;
            }
        }
        else if (n == 0) {
            nodeAtN = current;
            nodeAfterN = current->next;
        }
        return ret;
    }
    
private:
    ListNode *nodeAfterN;
    ListNode *nodeAtN;
};

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int end = inorder.size() - 1;
        if (end < 0) return NULL;
        return getRoot(inorder, postorder, 0, end, postorder[end], 0);
    }
    
    TreeNode *getRoot(vector &inorder, vector &postorder,
                 int start, int end, int rootVal, int offset) {
        if (start > end) return NULL;
        
        TreeNode *root = new TreeNode(rootVal);
        
        int rootPosInOrder = start;
        for (; rootPosInOrder < end; ++rootPosInOrder) {
            if (inorder[rootPosInOrder] == rootVal) break;
        }
        
        root->left = getRoot(inorder, postorder, start,
               rootPosInOrder - 1, postorder[rootPosInOrder - 1 + offset], offset);
        root->right = getRoot(inorder, postorder, rootPosInOrder + 1,
              end, postorder[end - 1 + offset], offset - 1);
        return root;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int end = inorder.size() - 1;
        if (end < 0) return NULL;
        return getRoot(inorder, postorder, 0, end, 0);
    }
    
    TreeNode *getRoot(vector &inorder, vector &postorder, int start, int end, int offset) {
        if (start > end) return NULL;
        
        int rootVal = postorder[end + offset];
        TreeNode *root = new TreeNode(rootVal);
        
        int rootPosInOrder = start;
        for (; rootPosInOrder < end; ++rootPosInOrder) {
            if (inorder[rootPosInOrder] == rootVal) break;
        }
        
        root->left = getRoot(inorder, postorder, start, rootPosInOrder - 1, offset);
        root->right = getRoot(inorder, postorder, rootPosInOrder + 1, end, offset - 1);
        return root;
    }
};

Balanced Binary Tree

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

» Solve this problem

Complexity: O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rootDepth = 0;
        return _isBalanced(root, rootDepth);
    }
    
    bool _isBalanced(TreeNode *root, int& depth) {
        if (!root) return true;
        
        int leftDepth = depth + 1;
        int rightDepth = depth + 1;
        bool subTreeResult = _isBalanced(root->left, leftDepth)
            && _isBalanced(root->right, rightDepth);
            //trigger recursion first to avoid computation of depth
            //until we reach the leaf node
        
        depth = max(leftDepth, rightDepth);
           //recursively update parent depth, bottom-up 
        if (subTreeResult && abs(leftDepth - rightDepth) <= 1) {
            return true;
        }
        else {
            return false;
        }
    }
};

Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

Complexity: O(n^2)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = 0;
        ListNode *node = head;
        while (node) {
            ++n;
            node = node->next;
        }
        return toBST(head, n);
    }
    
    // n - the total number of nodes needs processing
    TreeNode *toBST(ListNode *head, int n) {
        if (!head || n <= 0) return NULL;
        
        int mid = n / 2;
        ListNode *midNode = head;
        for (int i = 0; i < mid; ++i) {
            midNode = midNode->next;
        }
        
        TreeNode *root = new TreeNode(midNode->val);
        root->left = toBST(head, mid);
        root->right = toBST(midNode->next, n - mid - 1);
        return root;
    }
};

Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

Complexity: O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return toBST(num, 0, num.size() - 1);
    }
    
    TreeNode *toBST(vector &num, int start, int end) {
        if (end < start) {
            return NULL;
        }
        
        int mid = (start + end) / 2;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = toBST(num, start, mid - 1);
        root->right = toBST(num, mid + 1, end);
        return root;
    }
};