[LeetCode] 212. Word Search II

https://leetcode.com/problems/word-search-ii/

Word Search II - LeetCode

Word Search II.

 

 

항상 daily 문제를 풀떄면 Easy 난이도의 문제가 걸리길 바란다.

하지만 오늘 걸린것은 Hard.. 

문제를 보니 그제 풀었던 Word Search의 확장판이었다.

보통 확장판으로 나온 문제들은 테스트 케이스와 제한조건이 더 복잡해지며

기존 코드를 넣으면 시간초과나 메모리 초과가 뜨기마련이다.

역시나 기존 코드를 돌렸더니 시간초과가 발생했다.

어디서 시간초과가 발생할지 살펴보니

최대 길이(10)로 주어진 문자열이 끝부분만 살짝 살짝 다른 케이스들이 쭉 있었다.

기존 코드는 비슷한 문자열이 주어져도 처음부터 탐색하니 여기에 시간초과 해결 실마리가 있겠다 생각했다.

비슷한 문자열을 처리하는 방법에는.. 바로 어제 풀었던 Trie 알고리즘이 있다.

어쩌면 순서가 노리고 만들어진게 아닐까 싶어 바로 Trie 알고리즘을 구현하였다.

 

순서는

 

1. Trie 알고리즘 구현

2-1. Input에서 words 로 주어진 단어들을 Trie 에 저장

2-2. 이 때, Trie에는 다음 알파벳을 나타내는 26개의 Trie 포인터와 현재 알파벳이 끝글자임을 나타내는 val 을 넣어준다.

2-3. Trie 초기화시에는 val은 0으로, 26개의 Trie 포인터는 NULL로 초기화해준다.

3. 기존 search 코드를 이용하여 Trie를 하나씩 훑으며 val 이 1일 경우 ret 벡터에 저장하며 val을 0으로 변경

 

Trie도 스스로 구현하고 (어제보다는 간단하고 class가 아닌 구조체로 구현했지만)

응용문제로 나와 꽤 좋은 문제고 발전이 느껴졌다.

 

전체 코드는 아래와 같다.

class Solution {
public:
    struct Trie{
        int val;
        Trie* next[26];
        Trie() {
            this->val = 0;
            for (int i=0; i<26; i++) this->next[i] = NULL;
        }
    };
    vector<string> ret;
    vector<vector<char>> board;
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie* root = new Trie();
        Trie* cur;
        for (auto word:words) {
            cur = root;
            for (int i=0; i<word.size(); i++) {
                if (cur->next[word[i]-'a']==NULL) cur->next[word[i]-'a'] = new Trie();
                cur = cur->next[word[i]-'a'];
            }
            cur->val = 1;
        }  
        cur = root;
        int chk[12][12];
        this->board = board;
        for (int i=0; i<12; i++) for (int j=0; j<12; j++) chk[i][j] = 0;
        for (int i=0; i<26; i++) {
            if (cur->next[i]==NULL) continue;
            string temp = "";
            temp += (char)i + 'a';
            for (int j=0; j<this->board.size(); j++) {
                for (int k=0; k<this->board[j].size(); k++) {
                    if (board[j][k]==i+'a') {
                        search(cur->next[i], make_pair(j,k), chk, temp);
                    }
                }
            }
        }
        return this->ret;
    }
    void search(Trie* cur, pair<int,int> pos, int chk[12][12], string word) {
        int y = pos.first, x = pos.second;
        if (x<0 || y<0 || x==this->board[0].size() || y==this->board.size() || chk[y][x]==1 || word[word.size()-1] != this->board[y][x]) return;
        chk[y][x] = 1;
        if (cur->val) {
            this->ret.push_back(word);
            cur->val = 0;
        }
        for (int i=0; i<26; i++) {
            if (cur->next[i]==NULL) continue;
            string temp = word+(char)(i+'a');
            search(cur->next[i],make_pair(y-1,x),chk, temp);
            search(cur->next[i],make_pair(y,x-1),chk, temp);
            search(cur->next[i],make_pair(y+1,x),chk, temp);
            search(cur->next[i],make_pair(y,x+1),chk, temp);
        }  
        chk[y][x] = 0;
    }
};