2490. Circular Sentence - Detailed Explanation

Problem Statement

A sentence is given as a string consisting of one or more words separated by single spaces. A sentence is considered circular if the following conditions hold:

1. For every adjacent pair of words in the sentence, the last character of the first word is the same as the first character of the next word.

2. Additionally, the last character of the last word must be the same as the first character of the first word.

The task is to determine if the given sentence is circular.

Detailed Explanation

How to Determine if a Sentence is Circular

1. Splitting the Sentence:

   • First, split the input string by spaces to obtain a list of words.
   • For example, if the sentence is "leetcode exercises sound delightful", splitting it yields:
     ["leetcode", "exercises", "sound", "delightful"].

2. Checking Adjacent Words:

   • For every pair of consecutive words, check if the last character of the current word matches the first character of the next word.
   • In our example:
     • Check if the last character of "leetcode" (which is 'e') matches the first character of "exercises" (which is 'e').
     • Then, check if the last character of "exercises" (which is 's') matches the first character of "sound" (which is 's').
     • Next, check if the last character of "sound" (which is 'd') matches the first character of "delightful" (which is 'd').

3. Circular Check for the First and Last Words:

   • After checking all adjacent pairs, verify that the last character of the last word equals the first character of the first word.
   • In our example, check if the last character of "delightful" (which is 'l') matches the first character of "leetcode" (which is 'l').

4. Return the Result:

   • If all these conditions are met, the sentence is circular and the function should return true; otherwise, it returns false.

Example Walkthrough

Example 1

• Input: "leetcode exercises sound delightful"
• Processing:
  • Split into words: ["leetcode", "exercises", "sound", "delightful"]
  • Check adjacent pairs:
    • "leetcode" ends with 'e', "exercises" starts with 'e' → ✓
    • "exercises" ends with 's', "sound" starts with 's' → ✓
    • "sound" ends with 'd', "delightful" starts with 'd' → ✓
  • Check circular condition:
    • "delightful" ends with 'l', "leetcode" starts with 'l' → ✓
• Output: true

Example 2

• Input: "arc code"
• Processing:
  • Split into words: ["arc", "code"]
  • Check adjacent pair:
    • "arc" ends with 'c', "code" starts with 'c' → ✓
  • Check circular condition:
    • "code" ends with 'e', "arc" starts with 'a' → ✗
• Output: false

Approach Summary

1. Split the Sentence:

   • Use the split function to get a list of words.

2. Iterate Through Adjacent Words:

   • Loop over the words list and compare the last character of the current word with the first character of the next word.

3. Circular Check:

   • After the loop, compare the last character of the final word with the first character of the first word.

4. Return Boolean Result:

   • If all checks pass, the sentence is circular; otherwise, it is not.

Time and Space Complexity

• Time Complexity:
  O(n), where n is the number of words (or more precisely, the number of characters in the sentence) because we iterate through the words once and perform constant time checks for each pair.

• Space Complexity:
  O(n) for storing the split words. The additional space usage is proportional to the number of words.