2490. Circular Sentence

A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

• For example, "Hello World", "HELLO", "hello world hello world" are all sentences.

Words consist of only uppercase and lowercase English letters. Uppercase and lowercase English letters are considered different.

A sentence is circular if:

• The last character of a word is equal to the first character of the next word.
• The last character of the last word is equal to the first character of the first word.

For example, "leetcode exercises sound delightful", "eetcode", "leetcode eats soul" are all circular sentences. However, "Leetcode is cool", "happy Leetcode", "Leetcode" and "I like Leetcode" are not circular sentences.

Given a string sentence, return true if it is circular. Otherwise, return false.

Example 1:

Input: sentence = "leetcode exercises sound delightful"
Output: true
Explanation: The words in sentence are ["leetcode", "exercises", "sound", "delightful"].
- leetcode's last character is equal to exercises's first character.
- exercises's last character is equal to sound's first character.
- sound's last character is equal to delightful's first character.
- delightful's last character is equal to leetcode's first character.
The sentence is circular.

Example 2:

Input: sentence = "eetcode"
Output: true
Explanation: The words in sentence are ["eetcode"].
- eetcode's last character is equal to eetcode's first character.
The sentence is circular.

Example 3:

Input: sentence = "Leetcode is cool"
Output: false
Explanation: The words in sentence are ["Leetcode", "is", "cool"].
- Leetcode's last character is not equal to is's first character.
The sentence is not circular.

Constraints:

• 1 <= sentence.length <= 500
• sentence consist of only lowercase and uppercase English letters and spaces.
• The words in sentence are separated by a single space.
• There are no leading or trailing spaces.

Approach 01:

#include <string>
#include <vector>
#include <sstream>

class Solution {
public:
    bool isCircularSentence(const std::string& sentence) {
        std::vector<std::string> words;
        std::istringstream stream(sentence);
        std::string word;
        
        while (stream >> word) {
            words.push_back(word);
        }
        
        std::string firstLettersConcat;
        std::string shiftedLastLetters;
        
        for (const auto& w : words) {
            firstLettersConcat += w.front();
            shiftedLastLetters += w.back();
        }
        
        int sentenceLength = shiftedLastLetters.size();
        shiftedLastLetters = shiftedLastLetters.back() + shiftedLastLetters.substr(0, sentenceLength - 1);
        
        return shiftedLastLetters == firstLettersConcat;
    }
};

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        words = sentence.split(" ")
        firstLettersConcat = ''
        shiftedLastLetters = ''
        
        for word in words:
            firstLettersConcat += word[0]
            shiftedLastLetters += word[-1]
        
        sentenceLength = len(shiftedLastLetters)
        shiftedLastLetters = shiftedLastLetters[-1] + shiftedLastLetters[:sentenceLength - 1]
        
        return shiftedLastLetters == firstLettersConcat

Time Complexity

• Splitting Sentence into Words:

  Splitting the input sentence into words using std::istringstream takes \( O(N) \), where \( N \) is the length of the sentence.

• Concatenating First and Last Letters:

  Iterating through each word to build firstLettersConcat and shiftedLastLetters involves going through each word, making this step also \( O(N) \).

• Shifting Last Letters:

  Shifting the last letters to create shiftedLastLetters requires taking the last character and concatenating it with the rest. This operation has a complexity of \( O(N) \) as well.

• Overall Time Complexity:

  The combined time complexity is \( O(N) + O(N) + O(N) = O(N) \).

Space Complexity

• Storage for Words:

  The words vector stores all words from the sentence, resulting in a space complexity of \( O(N) \).

• Concatenated Strings:

  Both firstLettersConcat and shiftedLastLetters store a sequence of characters with a length equal to the number of words, contributing an additional \( O(N) \) space usage.

• Overall Space Complexity:

  Since both the words vector and the concatenated strings are of size \( O(N) \), the overall space complexity is \( O(N) \).