2490. Circular Sentence - Explanation

Problem Link

1. Splitting the String

Intuition

A sentence is circular if the last character of each word matches the first character of the next word, and the last word connects back to the first. By splitting the sentence into individual words, we can check each consecutive pair. Using modular indexing, we naturally handle the wrap-around from the last word to the first word in a single loop.

Algorithm

1. Split the sentence by spaces to get an array of words.
2. Iterate through each word at index i from 0 to n-1.
3. For each word, compare its first character with the last character of the previous word at index (i-1+n) % n.
4. If any pair does not match, return false.
5. If all pairs match, return true.

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        w = sentence.split(" ")

        for i in range(len(w)):
            if w[i][0] != w[i - 1][-1]:
                return False

        return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

2. Iteration (Space Optimized)

Intuition

Instead of splitting the string and storing all words, we can iterate through the sentence and check only the characters around each space. When we find a space, the character before it is the last character of the previous word, and the character after it is the first character of the next word. We also need to check that the first and last characters of the entire sentence match for the circular connection.

Algorithm

1. Iterate through each character in the sentence.
2. When a space is found at index i, compare sentence[i-1] (end of previous word) with sentence[i+1] (start of next word).
3. If they do not match, return false.
4. After the loop, check if the first character of the sentence equals the last character.
5. Return true if all checks pass.

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        for i in range(len(sentence)):
            if sentence[i] == " " and sentence[i - 1] != sentence[i + 1]:
                return False
        return sentence[0] == sentence[-1]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$