Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6219841

Browse files
committed
[Function add]
1. Add leetcode results in C++.
1 parent239b3ce commit6219841

File tree

2 files changed

+182
-1
lines changed

2 files changed

+182
-1
lines changed

‎leetcode/212. Word Search II.md

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -249,3 +249,135 @@ class Solution {
249249
}
250250
}
251251
```
252+
253+
###C++ version
254+
* Method 1: dfs
255+
```objectivec
256+
class Solution {
257+
private:
258+
vector<string> res_;
259+
static int dir[4][2];
260+
vector<vector<char>> board_;
261+
int height_, width_;
262+
bool dfs(int index, const string& word, int row, int col){
263+
if(index == word.length()) return true;
264+
int tx = 0, ty = 0;
265+
for(int d = 0; d < 4; ++d){
266+
tx = row + Solution::dir[d][0];
267+
ty = col + Solution::dir[d][1];
268+
if(tx >= 0 && tx < height_ && ty >= 0 && ty < width_ && board_[tx][ty] != '#' && board_[tx][ty] == word[index]){
269+
char c = board_[tx][ty];
270+
board_[tx][ty] = '#';
271+
if(dfs(index + 1, word, tx, ty)){
272+
board_[tx][ty] = c;
273+
return true;
274+
}
275+
board_[tx][ty] = c;
276+
}
277+
}
278+
return false;
279+
}
280+
public:
281+
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
282+
height_= board.size();
283+
width_ = board[0].size();
284+
board_ = move(board);
285+
unordered_set<string> set(words.begin(), words.end());
286+
for(const string& word: set){
287+
bool found = false;
288+
for(int i = 0; i < height_ && !found; ++i){
289+
for(int j = 0; j < width_ && !found; ++j){
290+
if(word[0] == board_[i][j]){
291+
char c = board_[i][j];
292+
board_[i][j] = '#';
293+
if(dfs(1, word, i, j)){
294+
res_.emplace_back(word);
295+
found = true;
296+
}
297+
board_[i][j] = c;
298+
}
299+
}
300+
}
301+
}
302+
return res_;
303+
}
304+
};
305+
int Solution::dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
306+
static auto speedup=[](){
307+
ios::sync_with_stdio(false);
308+
cin.tie(nullptr);
309+
cout.tie(nullptr);
310+
return nullptr;
311+
}();
312+
```
313+
314+
* Method 2: Tire Tree
315+
```objectivec
316+
struct Node{
317+
vector<Node*> childs;
318+
const string* word;
319+
320+
Node(): childs(26), word(nullptr){}
321+
~Node(){
322+
for(auto node: childs){
323+
delete node;
324+
}
325+
}
326+
};
327+
class Solution {
328+
private:
329+
unique_ptr<Node> root_;
330+
331+
void insert(const string& word){
332+
Node* temp = root_.get();
333+
for(const char& c: word){
334+
if(!temp->childs[c - 'a']){
335+
temp->childs[c - 'a'] = new Node();
336+
}
337+
temp = temp->childs[c - 'a'];
338+
}
339+
temp->word = &word;
340+
}
341+
static int dir[4][2];
342+
public:
343+
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
344+
root_.reset(new Node());
345+
for(const string& word: words){
346+
insert(word);
347+
}
348+
int height = board.size(), width = board[0].size();
349+
vector<string> res;
350+
function<void(int, int, Node*)> walk = [&](int i, int j, Node* node){
351+
if(i < 0 || i >= height || j < 0 || j >= width || board[i][j] == '#') return;
352+
const char c = board[i][j];
353+
Node* next = node->childs[c - 'a'];
354+
if(!next) return;
355+
if(next->word){
356+
res.emplace_back(*next->word);
357+
next->word = nullptr;
358+
}
359+
int tx = 0, ty = 0;
360+
board[i][j] = '#';
361+
for(int d = 0; d < 4; ++d){
362+
tx = i + dir[d][0];
363+
ty = j + dir[d][1];
364+
walk(tx, ty, next);
365+
}
366+
board[i][j] = c;
367+
};
368+
for(int i = 0; i < height; ++i){
369+
for(int j = 0; j < width; ++j){
370+
walk(i, j, root_.get());
371+
}
372+
}
373+
return res;
374+
}
375+
};
376+
int Solution::dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
377+
static auto speedup=[](){
378+
ios::sync_with_stdio(false);
379+
cin.tie(nullptr);
380+
cout.tie(nullptr);
381+
return nullptr;
382+
}();
383+
```

‎leetcode/79. Word Search.md

Lines changed: 50 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -256,4 +256,53 @@ class Solution {
256256
return false;
257257
}
258258
}
259-
```
259+
```
260+
261+
###C++ version
262+
* Method 1: dfs
263+
```objectivec
264+
class Solution {
265+
private:
266+
static int dir[4][2];
267+
vector<vector<char>> board_;
268+
int height, width;
269+
bool dfs(const string& word, int index, int i, int j, vector<vector<int>>& visited){
270+
if(index == word.length()) return true;
271+
int tx = 0, ty = 0;
272+
for(int d = 0; d < 4; ++d){
273+
tx = i + Solution::dir[d][0];
274+
ty = j + Solution::dir[d][1];
275+
if(tx >= 0 && tx < height && ty >= 0 && ty < width && !visited[tx][ty] && word[index] == board_[tx][ty]){
276+
visited[tx][ty] = true;
277+
if(dfs(word, index + 1, tx, ty, visited)) return true;
278+
visited[tx][ty] = false;
279+
}
280+
}
281+
return false;
282+
}
283+
public:
284+
bool exist(vector<vector<char>>& board, string word) {
285+
this->height = board.size();
286+
this->width = board[0].size();
287+
board_ = move(board);
288+
vector<vector<int>> visited(height, vector<int>(width, false));
289+
for(int i = 0; i < height; ++i){
290+
for(int j = 0; j < width; ++j){
291+
if(word[0] == board_[i][j]){
292+
visited[i][j] = true;
293+
if(dfs(word, 1, i, j, visited)) return true;
294+
visited[i][j] = false;
295+
}
296+
}
297+
}
298+
return false;
299+
}
300+
};
301+
int Solution::dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
302+
static auto speedup=[](){
303+
ios::sync_with_stdio(false);
304+
cin.tie(nullptr);
305+
cout.tie(nullptr);
306+
return nullptr;
307+
}();
308+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp