Surrounded Regions

Surrounded RegionsFeb 22

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Idea: BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (board.size() <= 1) return;
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        vector<vector<bool>> checked(rows, vector<bool>(cols, false));
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (!visited[i][j]) {
                    if (board[i][j] == 'O') {
                        if (checkIfSurrounded(i, j, board, visited, checked)) {
                            markChecked(i, j, board, checked);
                        }
                    }
                    else {
                        visited[i][j] = true;
                    }
                }
            }
        }
    }
    
    bool checkIfSurrounded(int i, int j, vector<vector<char>> &board,
        vector<vector<bool>> &visited, vector<vector<bool>> &checked) {
        queue<Pos> q;
        bool result = true;
        
        q.push(Pos(i, j));
        visited[i][j] = true;
        
        while (!q.empty()) {
            Pos pos = q.front();
            q.pop();
            i = pos.row;
            j = pos.col;
            checked[i][j] = true;
            
            if (j - 1 >= 0) {
                if (board[i][j - 1] == 'O' && !visited[i][j - 1]) {
                    q.push(Pos(i, j - 1));
                    visited[i][j - 1] = true;
                }
            }
            else {
                result = false;
            }
            
            if (j + 1 < board[0].size()) {
                if (board[i][j + 1] == 'O' && !visited[i][j + 1]) {
                    q.push(Pos(i, j + 1));
                    visited[i][j + 1] = true;
                }
            }
            else {
                result = false;
            }
            
            if (i + 1 < board.size()) {
                if (board[i + 1][j] == 'O' && !visited[i + 1][j]) {
                    q.push(Pos(i + 1, j));
                    visited[i + 1][j] = true;
                }
            }
            else {
                result = false;
            }
            
            if (i - 1 >= 0) {
                if (board[i - 1][j] == 'O' && !visited[i - 1][j]) {
                    q.push(Pos(i - 1, j));
                    visited[i - 1][j] = true;
                }
            }
            else {
                result = false;
            }
        }
 
        return result;
    }
    
    void markChecked(int i, int j, vector<vector<char>> &board,
        vector<vector<bool>> &checked) {
        queue<Pos> q;
        bool result = true;
        
        q.push(Pos(i, j));
        
        while (!q.empty()) {
            Pos pos = q.front();
            q.pop();
            i = pos.row;
            j = pos.col;
            
            board[i][j] = 'X';
            checked[i][j] = false;
            
            if (j - 1 >= 0) {
                if (checked[i][j - 1]) {
                    q.push(Pos(i, j - 1));
                    checked[i][j - 1] = false;
                }
            }
            
            if (j + 1 < board[0].size()) {
                if (checked[i][j + 1]) {
                    q.push(Pos(i, j + 1));
                    checked[i][j + 1] = false;
                }
            }
            
            if (i + 1 < board.size()) {
                if (checked[i + 1][j]) {
                    q.push(Pos(i + 1, j));
                    checked[i + 1][j] = false;
                }
            }
            
            if (i - 1 >= 0) {
                if (checked[i - 1][j]) {
                    q.push(Pos(i - 1, j));
                    checked[i - 1][j] = false;
                }
            }
        }
    }
    
    typedef struct Pos {
        int row, col;
        Pos(int i, int j): row(i), col(j) {};
    };
};

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