[Leetcode 648번 문제] 648. Replace Words

 

문제 상황

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

영어에서 root라는 것이 있는데 특정 원형 단어로 유도된 더 긴 단어들을 의미한다. 여기서 dictionary에 root단어들이 주어진다. 그리고 문장 sentence가 주어진다. sentences의 파생어들을 전부 root의 언어로 바꿔라.

한 단어가 두가지 어원으로 교체할 수 있을 경우에는 하나로 바꾼다.

입력

문자열 배열, dictionary

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case letters.

문자열 sentence

길이는 최대 100만

단어의 개수는 1부터 1000

각각의 단어의 길이는 1부터 1000

모든 단어는 공백으로 구분됨

출력

변형된 문자열 s

과정

1. 단어 배열을 작은 순으로 정렬
2. 단어의 개수를 정렬

크게 말한다면 이렇게 할 수 있겠다.

dictionary 배열 정렬

sentence 문자열을 배열로 정렬

sentence 배열만큼 on,off 가지는 배열 생성

모든 Dictionary 안의 root에 대해서 앞에서부터 차례로 모든 sentence를 찾음

C++과 문자열

C++의 문자열의 Join - 없다 그게 슬픔

알고리즘 개요도

알고리즘

class Solution {
    vector<string> sentences  = {};
    vector<int> sentencesOV = vector<int> (1000, 0);
public:
    string replaceWords(vector<string>& dictionary, string sentence) {

        sort(dictionary.begin(), dictionary.end());
        string word = "";
        for (char c : sentence)
        {
            if (c != ' ')
            {
                word += c;
            }
            else
            {   
                // string newword = word;
                cout << word << '\n';
                sentences.push_back(word);
                word = "";
            }
        }
        sentences.push_back(word);

        for (string root : dictionary)
        {
            for (int idx = 0; idx < sentences.size(); idx++)
            {
                bool isDeriviated = true;
                if (sentencesOV[idx] == 1 || root.length() > sentences[idx].length())
                {
                    continue;
                }
                for (int c = 0; c < root.length(); c++)
                {
                    if (sentences[idx][c] != root[c])
                    {
                        isDeriviated = false;
                        break;
                    }
                }
                if (isDeriviated)
                {
                    sentences[idx] = root;
                    sentencesOV[idx] = 1;
                }
            }
        }
        string ans = "";
        for (int wordindex = 0; wordindex < sentences.size(); wordindex++)
        {
            ans += sentences[wordindex];
            if (wordindex == sentences.size() - 1)
                break;
            ans += ' ';
        }
        return ans;
    }
};