algoadvance

Given a string s, determine if it is a circular sentence. A sentence is considered circular if:

  1. The last character of each word in the sentence is the same as the first character of the next word.
  2. The last character of the last word is the same as the first character of the first word.

The string s consists of lowercase English letters and spaces ''.

Return True if s is a circular sentence. Otherwise, return False.

Clarifying Questions

  1. Can the input string have leading or trailing spaces?
    • You can assume no leading or trailing spaces, and words are separated by a single space.
  2. What is the length of the input string?
    • The input string can be up to 10^5 characters long.
  3. Can the input string contain any special characters?
    • No, the input string consists only of lowercase English letters and spaces.
  4. How should we handle edge cases such as a single word?
    • A single word should be considered circular as there is no transition between words.

Strategy

  1. Split the Input String into Words: Split the input string by spaces to get an array of words.
  2. Check Circular Condition:
    • Iterate through the words and for each word (except the last one), check if the last character of the current word matches the first character of the next word.
    • Finally, check if the last character of the last word matches the first character of the first word.

Code

def isCircularSentence(s: str) -> bool:
    # Split the sentence into words
    words = s.split()
    
    # If there's only one word, it's considered circular.
    if len(words) == 1:
        return True
    
    # Check the circular condition for each word
    for i in range(len(words) - 1):
        if words[i][-1] != words[i + 1][0]:
            return False
    
    # Check the circular condition between the last and the first word
    if words[-1][-1] != words[0][0]:
        return False
    
    return True

# Example Usage
s = "lazyly am marvelous"
print(isCircularSentence(s))  # Output: True

Time Complexity

The time complexity of this solution is O(n):

Thus, the overall complexity is O(n), where n is the length of the string.

Try our interview co-pilot at AlgoAdvance.com