Concatenated Words

1630 단어
제목은 최소한 두 개의 다른 문자열로 구성된 문자열을 구하는 문자열 그룹에서 나온 것입니다.나는 모든 문자열을 해시표에 넣고 옮겨다니는 것을 생각했지만, 옮겨다니는 과정에서 이 문자열이 우리가 찾는 문자열인지 아닌지를 어떻게 판단할지 몰랐다.그리고 이것은 DP 문제입니다. dp[i] 는 앞의 i 문자가 다른 문자열로 구성될 수 있음을 나타냅니다.dp[j] = 1 if dp[j-i] = 1 and s[i:j] belong to array 코드는 다음과 같습니다.
class Solution {
public:
    vector findAllConcatenatedWordsInADict(vector& words) {
        unordered_set s(words.begin(), words.end());
        vector res;
        for (auto word : words) {
            int n = word.size();
            vector dp(n+1, 0);
            dp[0] = 1;
            for (int i=0; i

그런 다음 토론 영역을 살펴보면 DP보다 조금 더 빠른 회상 방법도 있습니다. 코드는 다음과 같습니다.
class Solution {
public:
    vector findAllConcatenatedWordsInADict(vector& words) {
        unordered_set dic(words.begin(), words.end());
        vector res;
        for (int i = 0; i < words.size(); i++) {
            if (isConcatenated(words[i], dic, false)) res.push_back(words[i]);
        }
        return res;
    }
    
    bool isConcatenated(string word, unordered_set& dic, bool isSubstr) {
        if (word.empty()) return isSubstr;
        if (isSubstr && dic.count(word)) return true;
        for (int len=1;len

좋은 웹페이지 즐겨찾기