Problem of The Day: Circular Sentence

Problem Statement

Intuition

The problem requires checking if a sentence is “circular.” This likely involves looking at the boundaries of each word in the sentence and ensuring that each word ends with the same letter that the next word begins with, ultimately connecting the last word to the first.

Approach

1. Initial Checks: First, check if the sentence starts or ends with a space. If it does, we return False since a valid circular sentence should not have leading or trailing spaces.

2. Consecutive Space Check: As we loop through each character, we ensure that there are no consecutive spaces, as that would imply an invalid sentence structure with empty words. If any two consecutive characters are spaces, we return False.

3. Word-by-Word Validation: Split the sentence into words. For each word pair, check if the last character of the first word matches the first character of the next word. If not, return False.

4. Circular Check: Finally, confirm that the first character of the first word matches the last character of the last word, ensuring the sentence forms a loop.

Complexity

• Time Complexity: \(O(n)\), where \(n\) is the length of the sentence. This is because we iterate through the sentence once to validate spaces, then split and iterate again through each word to check adjacent characters.
• Space Complexity: \(O(m)\), where \(m\) is the number of words in the sentence, due to storing the split words in a list.

Code

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        # Check for leading or trailing spaces
        if sentence.startswith(' ') or sentence.endswith(' '):
            return False

        # Check for consecutive spaces within the sentence
        prev = ''
        for c in sentence:
            if c == ' ' and prev == ' ':
                return False
            prev = c

        # Split sentence into words and validate the circular condition
        words = sentence.split(' ')
        for i in range(len(words) - 1):
            if words[i][-1] != words[i + 1][0]:
                return False

        # Check that the sentence is circular
        return words[0][0] == words[-1][-1]

Editorial Solution

Approach 1: Split Sentence

class Solution:
    def isCircularSentence(self, sentence: str) -> bool:
        # Use the split function to store the words in a list.
        words = sentence.split(" ")
        n = len(words)

        # Start comparing from the last character of the last word.
        last = words[n - 1][-1]

        for i in range(n):
            # If this character is not equal to the first character of current word, return
            # false.
            if words[i][0] != last:
                return False
            last = words[i][-1]

        return True

Approach 2: Space-optimized Approach

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[len(sentence) - 1]