[LeetCode] 211 - Design Add and Search Words Data Structure

문제

• 링크: https://leetcode.com/problems/container-with-most-water
• 난이도: Medium
• 태그: 문자열, 깊이 우선 탐색, 설계, 트라이
• 결과: Time: 327 ms (72.95%), Space: 622.81 MB (19.33%)

풀이

class WordDictionary {
public:
    WordDictionary() {
        mRoot = make_unique<Node>();
    }
    
    void addWord(string word) {
        Node* curNode = mRoot.get();
		for (char c : word)
		{
            auto& child = curNode->children[c - 'a'];
    		if (child == nullptr)
			{
				child = make_unique<Node>();
			}

			curNode = child.get();
		}

		curNode->isWord = true;
    }
    
    bool search(string word) {
        return search_impl(word, mRoot.get());
    }

private:
	struct Node
	{
		bool isWord = false;
		unique_ptr<Node> children[26];
	};

	unique_ptr<Node> mRoot;

    bool search_impl(string_view word, Node* root)
    {
        Node* curNode = root;
		for (int i = 0; i < word.size(); ++i)
		{
            char c = word[i];
            if (c == '.')
            {
                for (auto& p : curNode->children)
                {
                    if (p != nullptr && search_impl(word.substr(i + 1), p.get()))
                    {
                        return true;
                    }
                }

                return false;
            }
            else
            {
                auto& child = curNode->children[c - 'a'];
                if (child == nullptr)
                {
                    return false;
                }

                curNode = child.get();
            }
		}

		return curNode->isWord;
    }
};

Trie 구현 문제인데, 와일드 카드 처리가 추가됐다. 처음엔 조금 고민했는데, 재귀로 해결했다. 문자열 복사 없는 substr 처리를 위해 인자는 std::string_view로 받았다. 와일드 카드 처리는 모든 자식을 순회하면 된다.

배운 점과 후기

Trie를 구현하는 것에 더해 와일드 카드 처리 같은 부수적인 처리를 구현해야하는 문제였다. LeetCode Premium에서는 해당 문제가 어떤 기업에서 출제됐는지 볼 수 있는데, FAANG 중 넷플릭스를 제외하면 최근까지도 여러번 출제한 모양이다. 이 정도로 결합된 문제도 충분히 풀 수 있도록 대비해야겠다.

이 포스트는 달레 스터디(6주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.