leetcode/daily111.cpp at main · iFangg/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
// Solution 1 - unfinished
class Solution {
public:
    bool areSentencesSimilar(string s1, string s2) {
        /*
        if s1 and s2 are initially equal, return true
        separate s1 and s2 into arrays of substrings/words
        find long and short strings
        loop through long str until first common word is found
            return false if common word is never found
            loop until uncommon word is found
                loop until common word is found
                    loop until uncommon words is found or end of string
                    if any more uncommon words are found, return false
                    else return true
        */
        if (s1 == s2)
            return false;

        auto words1 = std::vector<std::string>{};
        auto curr_word1 = std::string{};
        auto words2 = std::vector<std::string>{};
        auto curr_word2 = std::string{};
        auto longer = s1;
        auto shorter = s2;
        if (s2.size() > s1.size())
            std::swap(longer, shorter);

        for (auto i = 0; i < longer.size(); ++i) {
            if (longer[i] == ' ') {
                words1.push_back(curr_word1);
                curr_word1.clear();
            } else
                curr_word1 += longer[i];

            if (i < shorter.size()) {
                if (shorter[i] == ' ') {
                    words2.push_back(curr_word2);
                    curr_word2.clear();
                } else
                    curr_word2 += shorter[i];
            } else if (i == shorter.size() and !curr_word2.empty())
                words2.push_back(curr_word2);
        }

        if (!curr_word1.empty())
            words1.push_back(curr_word1);

        for (auto i = 0; i < words1.size(); ++i) {
            std::cout << words1[i] << ", ";
        }

        std::cout << std::endl;
        for (auto i = 0; i < words2.size(); ++i) {
            std::cout << words2[i] << ", ";
        }


        return false;
    }
}


// Solution 2
class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        // Helper function to split the sentence into words
        auto splitWords = [](const string& sentence) {
            vector<string> words;
            string word = "";
            for (char c : sentence) {
                if (c == ' ') {
                    if (!word.empty()) {
                        words.push_back(word);
                        word = "";
                    }
                } else {
                    word += c;
                }
            }
            if (!word.empty()) words.push_back(word);
            return words;
        };

        // Split both sentences into words
        vector<string> words1 = splitWords(sentence1);
        vector<string> words2 = splitWords(sentence2);

        // Ensure words1 is the longer sentence
        if (words1.size() < words2.size()) swap(words1, words2);

        int start = 0, end = 0;
        int n1 = words1.size(), n2 = words2.size();

        // Compare from the start
        while (start < n2 && words1[start] == words2[start]) start++;

        // Compare from the end
        while (end < n2 && words1[n1 - end - 1] == words2[n2 - end - 1]) end++;

        // Check if the remaining unmatched part is in the middle
        return start + end >= n2;
    }
};