<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}
/* 設定連結 */
a,
.open-files-container li.selected a {
color: #89FFF8;

}
a:hover,
.open-files-container li.selected a:hover {
color: #89FFF890;
}

</style>

###### tags: `Leetcode`

# 472. Concatenated Words

###### Link : https://leetcode.com/problems/concatenated-words/description/

## 題目
找到所有可被串接的字串
## 程式碼

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> ans;
        //存放所有存在的字串
        unordered_set<string> dictionary;
        for(string &word : words) 
            dictionary.insert(word);
        for(auto &word : words){
            const int n = word.size();
            //flag中1代表1以前的字串可被組成
            vector<bool> flag(n+1, 0);
            flag[0] = 1;
            for(int i = 0;i < n;i++){
                //如為0可直接跳過
                if(!flag[i]) continue;
                //判斷flag中1後面是否有可組成的字串
                for(int j = i + 1;j <= n;j++){
                    //j - i < n代表子字串長度不能超過原本的長度
                    //也就是自己不能被自己組成且存到答案中
                    if(j - i < n&&dictionary.count(word.substr(i, j - i))){
                        flag[j] = 1;
                    }
                }
                //如果整個字串已經可以被組成
                //可結束迴圈並存放答案
                if(flag[n]){
                    ans.push_back(word);
                    break;
                }
            }
        }
        return ans;
    }
};

## Date
### 2023/1/27