Surrounded Regions
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
------------------------------------------------------------------------------
Solution #1 dfs,
cannot pass the latest test case, which has size of 200*200
Slot that is neither on the borders or has no path leading to the borders is to be turned.
class Solution {
public:
void turn (int row, int col, vector<vector<char>> &board) {
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != 'O' ) {
return;
}
board[row][col] = 'T';
turn(row + 1, col, board);
turn(row - 1, col, board);
turn(row, col + 1, board);
turn(row, col - 1, board);
}
void solve(vector<vector<char>> &board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
for (int row = 0; row < m; row++) {
turn(row,0,board);
turn(row,n - 1,board);
}
for (int col = 0; col < n; col++) {
turn(0,col,board);
turn(m - 1,col,board);
}
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (board[row][col] == 'O') {
board[row][col] = 'X';
}else if (board[row][col] == 'T') {
board[row][col] = 'O';
}
}
}
}
};
Update on Nov-25-2014
Solution #2 another dfs,
cannot pass the latest test case, which is size of 200*200
class Solution {
public:
bool turn(vector<vector<char> > &board, vector<vector<bool> > &visit, int row, int col) {
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {
return false;
}
if (board[row][col] == 'X' || !visit[row][col]) {
return true;
}
visit[row][col] = false;
if (turn(board,visit,row - 1,col) && turn(board,visit,row + 1,col)
&& turn(board,visit,row,col - 1) && turn(board,visit,row,col + 1)) {
board[row][col] = 'X';
}
}
void solve(vector<vector<char>> &board) {
int rows = board.size();
if (rows == 0) return;
int cols = board[0].size();
vector<vector<bool> > visit(rows,vector<bool>(cols,true));
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (board[row][col] == 'O' && visit[row][col]) {
turn(board,visit,row,col);
}
}
}
}
};
Solution #3, bfs, similar approach as solution #1
class Solution {
public:
void turn (vector<vector<char>> &board, int row, int col) {
queue<pair<int,int>> que;
que.push(make_pair(row,col));
board[row][col] = 'T';
while (!que.empty()) {
row = que.front().first;
col = que.front().second;
que.pop();
if (row > 0 && board[row - 1][col] == 'O') {
que.push(make_pair(row - 1,col));
board[row - 1][col] = 'T';
}
if (row < board.size() - 1 && board[row + 1][col] == 'O') {
que.push(make_pair(row + 1,col));
board[row + 1][col] = 'T';
}
if (col > 0 && board[row][col - 1] == 'O') {
que.push(make_pair(row,col - 1));
board[row][col - 1] = 'T';
}
if (col < board[0].size() - 1 && board[row][col + 1] == 'O') {
que.push(make_pair(row,col + 1));
board[row][col + 1] = 'T';
}
}
}
void solve(vector<vector<char>> &board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
for (int i = 0; i < m; i++) {
if (board[i][n - 1] == 'O') {
turn(board,i,n - 1);
}
if (board[i][0] == 'O') {
turn(board,i,0);
}
}
for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') {
turn(board,0,i);
}
if (board[m - 1][i] == 'O') {
turn(board,m - 1,i);
}
}
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (board[row][col] == 'O') {
board[row][col] = 'X';
}else if (board[row][col] == 'T') {
board[row][col] = 'O';
}
}
}
}
};
Palindrome Partitioning II
Given a string
s, partition
s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of
s.
For example, given
s =
"aab",
Return
1 since the palindrome partitioning
["aa","b"] could be produced using 1 cut.
-------------------------------------------------------------------------
DP
dp[i] has the minimum cuts of string s[i : end]
if s[i : j], i <= j < n forms a palindrome, dp[i] = min(dp[i], dp[j] + 1)
watch out for the special case: s[i : end] is a palindrome
using dp for palindrome verification as well
class Solution {
public:
int minCut(string s) {
int n = s.length();
vector<int> dp(n + 1,0);
vector<vector<bool> > pal(n,vector<bool>(n,false));
// populate tables
for (int i = n - 1; i >= 0; i--) {
dp[i] = n - 1 - i;
for (int j = i; j < n; j++) {
if (s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])) {
pal[i][j] = true;
}
}
}
// dp
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (pal[i][j]) {
if (j == n-1) {
// special case: s[i:e] is a palindrome
// hence no cut needed
dp[i] = 0;
}
else {
dp[i] = min(dp[i],dp[j + 1] + 1);
}
}
}
}
return dp[0];
}
};
recursion with memoization
class Solution {
public:
bool isPal(string s) {
for (int i = 0; i < s.length() / 2; i++) {
if (s[i] != s[s.length() - 1 - i]) {
return false;
}
}
return true;
}
int cuts(string s, unordered_map<string,int> &dic) {
int minC = INT_MAX;
for (int i = 0; i < s.length() - 1; i++) {
string s1 = s.substr(0,i + 1);
string s2 = s.substr(i + 1);
int temp1 = 0;
int temp2 = 0;
if (dic.find(s1) != dic.end()) {
temp1 = dic[s1];
}else {
if (isPal(s1)) {
temp1 = 0;
}else {
temp1 = cuts(s1,dic);
}
dic[s1] = temp1;
}
if (dic.find(s2) != dic.end()) {
temp2 = dic[s2];
}else {
if (isPal(s2)) {
temp2 = 0;
}else {
temp2 = cuts(s2,dic);
}
dic[s2] = temp2;
}
minC = min(minC, temp1 + temp2 + 1);
}
dic[s] = minC;
return minC;
}
int minCut(string s) {
if (isPal(s)) return 0;
unordered_map<string,int> dic;
return cuts(s,dic);
}
};
Clone Graph
Clone an undirected graph. Each node in the graph contains a
label and a list of its
neighbors.
-----------------------------------------------------------
Typical BFS, can be solved iteratively by using a queue
Note: map new node to old node, updates have to be done with nodes stored in the map
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode* cpGraph (UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*,UndirectedGraphNode*>& mapping) {
if (mapping.find(node) != mapping.end()) {
return mapping[node];
}
UndirectedGraphNode *cp = new UndirectedGraphNode(node->label);
mapping[node] = cp;
mapping[node]->neighbors = node->neighbors;
for (int i = 0; i < node->neighbors.size(); i++) {
mapping[node]->neighbors[i] = cpGraph(node->neighbors[i],mapping);
}
return cp;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (node == NULL) return NULL;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mapping;
UndirectedGraphNode *cp = new UndirectedGraphNode(node->label);
mapping[node] = cp;
mapping[node]->neighbors = node->neighbors;
for (int i = 0; i < node->neighbors.size(); i++) {
mapping[node]->neighbors[i] = cpGraph(node->neighbors[i],mapping);
}
return cp;
}
};
Update on Dec-23-2014
refactoried
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *clone (UndirectedGraphNode *node,unordered_map<int,UndirectedGraphNode*> &dic) {
if (dic.find(node->label) != dic.end()) {
return dic[node->label];
}
UndirectedGraphNode *cp = new UndirectedGraphNode(node->label);
dic[node->label] = cp;
cp->neighbors = node->neighbors;
for (int i = 0; i < node->neighbors.size(); i++) {
cp->neighbors[i] = clone(node->neighbors[i],dic);
}
return cp;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == NULL) return NULL;
unordered_map<int,UndirectedGraphNode*> dic;
return clone(node,dic);
}
};
Update on Jun-23-2018
Java, bfs,
要记得存map！！！
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
Queue que = new LinkedList<>();
Map map = new HashMap<>();
que.add(node);
map.put(node, new UndirectedGraphNode(node.label));
while (!que.isEmpty()) {
UndirectedGraphNode top = que.poll();
UndirectedGraphNode clone = map.get(top);
for (UndirectedGraphNode n : top.neighbors) {
UndirectedGraphNode nClone;
if (map.containsKey(n)) {
nClone = map.get(n);
}else {
nClone = new UndirectedGraphNode(n.label);
que.add(n);
map.put(n, nClone);
}
clone.neighbors.add(nClone);
}
}
return map.get(node);
}
}
