Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Substring with Concatenation of All Words #53

Closed
Tracked by #100
fkdl0048 opened this issue Oct 4, 2024 · 0 comments
Closed
Tracked by #100

Substring with Concatenation of All Words #53

fkdl0048 opened this issue Oct 4, 2024 · 0 comments
Assignees
Labels
Milestone

Comments

@fkdl0048
Copy link
Owner

fkdl0048 commented Oct 4, 2024

using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        vector<string> wordPermutations;

        sort(words.begin(), words.end());

        do{
            string temp = "";
            for (auto word : words){
                temp += word;
            }
            wordPermutations.push_back(temp);
        }
        while (next_permutation(words.begin(), words.end()));

        int permutationLength = wordPermutations[0].length();
        int wordLength = words[0].length();

        for(int i = 0; i <= s.length() - permutationLength; i++){
            for(auto str : wordPermutations){
                if (str == s.substr(i, permutationLength)){
                    res.push_back(i);
                }
            }
        }

        return res;
    }
};
  • 내가 푼 풀이로는 words 개수가 증가함에 따라 비효율적으로 돌아가기 때문에 다른 방식을 써야 함
  • 아래에 작성된 솔루션인 슬라이딩 윈도우 기법을 활용해야 함 (아직은 어색하긴 한데, 다른 문제에 또 나올 듯 함)
class Solution {
    std::unordered_map<std::string, unsigned int> word_map;  // words 빈도 저장
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        std::vector<int> result;
        if (words.empty() || s.empty()) return result;

        unsigned int word_length = words[0].size();    // 각 단어의 길이
        unsigned int word_count = words.size();        // words의 단어 개수
        unsigned int total_length = word_length * word_count; // 찾아야 할 총 길이

        // 단어 빈도 맵을 초기화
        word_map.clear();
        for (const std::string& word : words)
            word_map[word]++;

        // 단어 길이만큼 offset을 돌면서 탐색
        for (unsigned int offset = 0; offset < word_length; ++offset) {
            unsigned int left = offset;
            std::unordered_map<std::string, unsigned int> seen;
            int valid_count = 0;

            // offset부터 끝까지 탐색, word_length씩 이동
            for (unsigned int right = offset; right + word_length <= s.size(); right += word_length) {
                std::string sub = s.substr(right, word_length);

                if (word_map.find(sub) != word_map.end()) {  // words에 있는 단어인 경우
                    seen[sub]++;
                    valid_count++;

                    // 단어의 빈도가 초과되면 윈도우를 축소
                    while (seen[sub] > word_map[sub]) {
                        std::string left_word = s.substr(left, word_length);
                        seen[left_word]--;
                        valid_count--;
                        left += word_length;
                    }

                    // 유효한 단어들이 모두 일치하는 경우
                    if (valid_count == word_count) {
                        result.push_back(left);
                    }
                } else {  // words에 없는 단어인 경우
                    seen.clear();
                    valid_count = 0;
                    left = right + word_length;
                }
            }
        }

        return result;
    }
};
@fkdl0048 fkdl0048 mentioned this issue Oct 4, 2024
7 tasks
@fkdl0048 fkdl0048 self-assigned this Oct 4, 2024
@fkdl0048 fkdl0048 added this to Todo Oct 4, 2024
@github-project-automation github-project-automation bot moved this to Todo in Todo Oct 4, 2024
@fkdl0048 fkdl0048 added this to the LeetCode milestone Oct 4, 2024
@fkdl0048 fkdl0048 moved this from Todo to Two-Week Plan in Todo Oct 4, 2024
@fkdl0048 fkdl0048 closed this as completed Oct 5, 2024
@github-project-automation github-project-automation bot moved this from Two-Week Plan to Done in Todo Oct 5, 2024
@fkdl0048 fkdl0048 mentioned this issue Oct 15, 2024
47 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Done
Development

No branches or pull requests

1 participant