472. Concatenated Words

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

이벤트(219.251) 2023.01.28 06:52:55

조회 34 추천 0 댓글 1

class Solution
{
public:
    struct trie
    {
        bool is_exist = false;
        bool is_end = false;
        vector<trie> childs;
    };
    trie *root;

    void make_tree(trie *current_t, string &s, int current_idx)
    {
        if (current_t->childs.size() == 0)
        {
            current_t->childs = vector<trie>(27);
        }
        char ch = s[current_idx];
        trie *next_t = &current_t->childs[ch - 'a'];
        next_t->is_exist = true;

        if (current_idx == s.size() - 1)
        {
            next_t->is_end = true;
            return;
        }
        return make_tree(next_t, s, current_idx + 1);
    }

    bool is_concatenated(trie *current_t, trie *check_t, string &s, int current_idx, int count)
    {
        if (s.size() == current_idx)
        {
            return 0 < count && check_t->is_end;
        }

        char ch = s[current_idx];
        trie *next_t = &current_t->childs[ch - 'a'];
        if (check_t->childs.size() == 0)
        {
            return is_concatenated(current_t, root, s, current_idx, count + 1);
        }

        trie *next_check_t = &check_t->childs[ch - 'a'];
        bool ret =  false;
        if (next_check_t->is_exist)
        {
            if(next_check_t->is_end) {
                ret |= is_concatenated(next_t, root, s, current_idx+1, count + 1);
            }
            if(ret) {
                return ret;
            }
            ret |= is_concatenated(next_t, next_check_t, s, current_idx+1, count);
        }
        return ret;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string> &words)
    {
        vector<string> ret;
        trie tree;
        tree.is_exist = true;
        root = &tree;

        for (auto &s : words)
        {
            make_tree(&tree, s, 0);
        }
        for (auto &s : words)
        {
            if (is_concatenated(&tree, &tree, s, 0, 0))
            {
                ret.push_back(s);
            }
        }
        return ret;
    }
};

if 덕지덕지..

처음엔 정렬하고 트리만들면서 체크하려고 했는데

그냥 트리만들고 체크함

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
156	2306. Naming a company (설명X) [1]	ㅇㅇ(218.234)	23.02.09	30	0
155	45. Jump Game II	이벤트(1.226)	23.02.08	21	0
154	45. Jump Game II	chromate00	23.02.08	22	0
153	45. Jump Game II	개발뉴비	23.02.08	28	0
151	904. Fruit Into Baskets	개발뉴비	23.02.08	30	0
148	904. Fruit Into Baskets	이벤트(1.226)	23.02.07	30	0
147	904. Fruit Into Baskets	chromate00	23.02.07	23	0
146	1470. Shuffle the Array	이벤트(1.226)	23.02.07	21	0
145	1470. Shuffle the Array	개발뉴비	23.02.06	31	0
143	1470. Shuffle the Array	chromate00	23.02.06	22	0
142	438. Find All Anagrams in a String	개발뉴비	23.02.05	32	0
141	438. Find All Anagrams in a String	chromate00	23.02.05	18	0
139	438. Find All Anagrams in a String	이벤트(1.226)	23.02.05	23	0
138	567. Permutation in String	개발뉴비	23.02.05	59	0
137	567. Permutation in String	이벤트(1.226)	23.02.04	23	0
136	567. Permutation in String [1]	chromate00	23.02.04	47	0
134	6. Zigzag Conversion.	chromate00	23.02.03	24	0
133	6. Zigzag Conversion	이벤트(1.226)	23.02.03	19	0
131	6. Zigzag Conversion	개발뉴비	23.02.03	30	0
130	953. Verifying an Alien Dictionary [1]	이벤트(1.226)	23.02.02	34	0
128	953. Verifying an Alien Dictionary	개발뉴비	23.02.02	41	0
127	953. Verifying an Alien Dictionary	chromate00	23.02.02	25	0
126	1071. Greatest Common Divisor of Strings	개발뉴비	23.02.02	27	0
125	1071. Greatest Common Divisor of Strings	이벤트(1.226)	23.02.01	36	0
123	1071. Greatest Common Divisor of Strings	chromate00	23.02.01	29	0
122	LeetCode 오늘의 문제 redirect 서비스	ㅇㅇ(1.229)	23.02.01	39	1
121	1626. Best Team With No Conflicts	이벤트(1.226)	23.01.31	23	0
119	1626. Best Team With No Conflicts [2]	chromate00	23.01.31	50	0
118	1137. N-th Tribonacci Number	개발뉴비	23.01.30	36	0
117	1137. N-th Tribonacci Number	이벤트(1.226)	23.01.30	19	0
116	1137. N-th Tribonacci Number	chromate00	23.01.30	21	0
113	352. Data Stream as Disjoint Intervals	개발뉴비	23.01.29	45	0
112	구글러에게 들은 코딩인터뷰 팁	ㅇㅇ(203.226)	23.01.28	63	0
111	352. Data Stream as Disjoint Intervals [1]	이벤트(219.251)	23.01.28	37	0
110	352. Data Stream as Disjoint Intervals [1]	chromate00	23.01.28	49	0
	472. Concatenated Words [1]	이벤트(219.251)	23.01.28	34	0
106	472. Concatenated Words [1]	개발뉴비	23.01.28	54	0
104	하드라니 오늘 풀 수 있을까	ㅇㅇ(118.235)	23.01.27	43	0
103	472. Concatenated Words	chromate00	23.01.27	43	0
101	787. Cheapest Flights Within K Stops	개발뉴비	23.01.26	32	0
100	787. Cheapest Flights Within K Stops	이벤트(219.251)	23.01.26	34	0
97	787. Cheapest Flights Within K Stops	chromate00	23.01.26	41	0
96	2359. Find Closest Node to Given Two Nod	이벤트(219.251)	23.01.26	38	0
95	2359. Find Closest Node to Given Two ~ [1]	개발뉴비	23.01.26	35	0
92	이벤트 너무 어려운데 힌트 봐도 되나요 [1]	이벤트(39.7)	23.01.25	73	0
91	2359. Find Closest Node to Given Two Nod	chromate00	23.01.25	36	0
90	53. Maximum Subarray	크아아아앙	23.01.25	32	0
89	45. Jump Game II	크아아아앙	23.01.25	26	0
88	55. Jump Game	크아아아앙	23.01.25	40	0
87	909. Snake and Ladders	chromate00	23.01.24	70	0