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.----------------------------------------------
class Solution {
public:
bool searchWord (vector<vector<char> > &board, string word, int cur, int row, int col,vector<vector<bool> > &mapping) {
int rowSize = board.size();
int colSize = board[0].size();
if (word.size() == cur) return true;
if (word.size() > cur) {
if (row > 0 && mapping[row-1][col] && word[cur] == board[row-1][col]) {
mapping[row-1][col] = false;
if (searchWord(board,word,cur+1,row-1,col,mapping)) {
return true;
}
mapping[row-1][col] = true;
}
if (row < rowSize-1 && mapping[row+1][col] && word[cur] == board[row+1][col]) {
mapping[row+1][col] = false;
if (searchWord(board,word,cur+1,row+1,col,mapping)) {
return true;
}
mapping[row+1][col] = true;
}
if (col < colSize-1 && mapping[row][col+1] && word[cur] == board[row][col+1]) {
mapping[row][col+1] = false;
if (searchWord(board,word,cur+1,row,col+1,mapping)) {
return true;
}
mapping[row][col+1] = true;
}
if (col > 0 && mapping[row][col-1] && word[cur] == board[row][col-1]) {
mapping[row][col-1] = false;
if (searchWord(board,word,cur+1,row,col-1,mapping)) {
return true;
}
mapping[row][col-1] = true;
}
}
return false;
}
bool exist(vector<vector<char> > &board, string word) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rowSize = board.size();
int colSize = board[0].size();
vector<vector<bool>> mapping(rowSize, vector<bool>(colSize, true));
for (int i=0;i<rowSize;i++) {
for (int j=0;j<colSize;j++) {
if (board[i][j] == word[0]) {
mapping[i][j] = false;
if (searchWord(board,word,1,i,j,mapping)) return true;
mapping[i][j] = true;
}
}
}
return false;
}
};
更新
class Solution {
public:
bool searchWord(vector<vector<char>>& board, string word,vector<vector<bool>> &visit,int index,int row,int col) {
if (index == word.length()) return true;
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()
|| visit[row][col] || word[index] != board[row][col]) {
return false;
}
visit[row][col] = true;
if(searchWord(board,word,visit,index + 1,row + 1,col)
|| searchWord(board,word,visit,index + 1,row - 1,col)
|| searchWord(board,word,visit,index + 1,row,col + 1)
|| searchWord(board,word,visit,index + 1,row,col - 1)) {
return true;
}
visit[row][col] = false;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int rowSize = board.size();
int colSize = board[0].size();
vector<vector<bool>> mapping(rowSize, vector<bool>(colSize, false));
for (int i=0; i<rowSize; i++) {
for (int j=0; j<colSize; j++) {
if (board[i][j] == word[0]) {
if (searchWord(board,word,mapping,0,i,j)) return true;
}
}
}
return false;
}
};
BFS理论上可行，但是需要记录太多信息 － 每个点的坐标，当前word的index，和一个额外的（独立的）visit的map。特别是这个map，因为不能backtracking，所有每条path都需要自己独立的map
Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given
1->2->3->3->4->4->5, return 1->2->5.Given
1->1->1->2->3, return 2->3.----------------------------------------------------------------------
Solution #1, iterative
watch out for the tailing number(s)
1,2,2 // cut off
1,2,2,3 // re-attach
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (head == NULL || head->next == NULL) return head;
ListNode *ret = NULL, *itr = head->next,*cur = head;
ListNode **pre = &ret; // a pointer to a pointer
while (itr != NULL) {
if (cur->val != itr->val) {
if (cur->next == itr) {
*pre = cur;
pre = &(cur->next);
cur = cur->next;
}else {
cur = itr;
}
}
itr = itr->next;
}
if (cur->next == NULL) { // include it if the last one is singular
*pre = cur;
}else { // otherwise, leave out the rest of the list
*pre = NULL;
}
return ret;
}
};
Solution #2 from internet, recursiveListNode *deleteDuplicates(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
// base case, 0, or 1 item in the list
if (head == NULL || head->next == NULL) return head;
ListNode *ret=NULL;
ListNode *cur = head;
int dup=0;
// remove duplicated values from head
while (cur->next != NULL && cur->val == cur->next->val)
{
ListNode *t=cur;
cur=cur->next;
delete(t);
dup = 1;
}
if (!dup)
{
ret = cur;
cur->next = deleteDuplicates(cur->next);
}
else
{
ret = deleteDuplicates(cur->next);
}
return ret;
}
Update on Sep-18-2014 A simpler version of solution #1
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (head == NULL || head->next == NULL) return head;
ListNode *dummy = new ListNode(INT_MIN);
dummy->next = head;
ListNode *pre = dummy;
while (head != NULL && head->next != NULL) {
if (head->val != head->next->val) {
pre = head;
head = head->next;
}else {
while (head->next != NULL && head->val == head->next->val) {
head = head->next;
}
pre->next = head->next;
head = head->next;
}
}
return dummy->next;
}
};
No comments:
Post a Comment