[LeetCode] 1813. Sentence Similarity III

https://leetcode.com/problems/sentence-similarity-iii/description/?envType=daily-question&envId=2024-10-06

leetcode - Sentence Similarity III

문제 유형 : 문자열 처리, 투 포인터

문제 난이도 : Medium

 

문제

You are given two strings sentence1 and sentence2, each representing a sentence composed of words. A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English characters.

Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. Note that the inserted sentence must be separated from existing words by spaces.

For example,

• s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.
• s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not separated from "Frog" by a space.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

 

두 문자열 s1과 s2가 주어진다.

두 문자열중에는 하나의 문장을 삽입할 수 있는데, 만약 하나의 문장을 삽입해서 두 문자열을 갈게 할 수 있다면, 비슷한 문자열이다.

두 문자열이 비슷하면 true를, 아니면 false를 반환하시오.

 

풀이

우선, 띄어쓰기로 구분해서 단어들을 배열에 담는다.

그리고, 왼쪽끝부터 비교해서 어디까지 같은지와,

오른쪽끝부터 비교해서 어디까지 같은지를 비교한다.

즉, 인덱스 변수 left는 왼쪽우선으로 보았을 때 막히는 부분, 즉 더 작은쪽의 prefix가 어디까지 prefix가 될 수 있는지다.

right는 오른쪽우선으로 비교했을 때 막히는 부분, 즉 더 작은쪽의 postfix가 어디까지 postfix가 될 수 있는지다.

 

만약 left가 right보다 커진다면, 1개 이하의 문장 삽입이 필요하다는 의미이고,

그렇지 않다면, 2개 이상의 문장 삽입이 필요하다거나 아예 만들지 못한다는 뜻이다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    vector<string> split(string &sentence) {
        stringstream ss(sentence);
        string word;
        vector<string> arr;
        while(ss >> word) {
            arr.push_back(word);
        }
        return arr;
    }
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        auto arr1 = split(sentence1);
        auto arr2 = split(sentence2);

        if(arr1.size() > arr2.size()) swap(arr1, arr2);

        int n = arr1.size();
        int m = arr2.size();

        int left = 0, right = n-1;
        while(left < n && arr1[left] == arr2[left]) left++;
        while(right >= 0 && arr1[right] == arr2[right + m - n]) right--;

        return left > right;
    }
};