2490. 回环句

难度: 简单

来源: 每日一题2023.06.30

---

句子 是由单个空格分隔的一组单词，且不含前导或尾随空格。

例如，"Hello World"、"HELLO"、"hello world hello world" 都是符合要求的句子。
单词 仅 由大写和小写英文字母组成。且大写和小写字母会视作不同字符。

如果句子满足下述全部条件，则认为它是一个 回环句 ：

单词的最后一个字符和下一个单词的第一个字符相等。
最后一个单词的最后一个字符和第一个单词的第一个字符相等。
例如，"leetcode exercises sound delightful"、"eetcode"、"leetcode eats soul" 都是回环句。然而，"Leetcode is cool"、"happy Leetcode"、"Leetcode" 和 "I like Leetcode" 都 不 是回环句。

给你一个字符串 sentence ，请你判断它是不是一个回环句。如果是，返回 true ；否则，返回 false 。

 

示例 1：

输入：sentence = "leetcode exercises sound delightful"
输出：true
解释：句子中的单词是 ["leetcode", "exercises", "sound", "delightful"] 。
- leetcode 的最后一个字符和 exercises 的第一个字符相等。
- exercises 的最后一个字符和 sound 的第一个字符相等。
- sound 的最后一个字符和 delightful 的第一个字符相等。
- delightful 的最后一个字符和 leetcode 的第一个字符相等。
这个句子是回环句。

示例 2：

输入：sentence = "eetcode"
输出：true
解释：句子中的单词是 ["eetcode"] 。
- eetcode 的最后一个字符和 eetcode 的第一个字符相等。
这个句子是回环句。

示例 3：

输入：sentence = "Leetcode is cool"
输出：false
解释：句子中的单词是 ["Leetcode", "is", "cool"] 。
- Leetcode 的最后一个字符和 is 的第一个字符 不 相等。 
这个句子 不 是回环句。

提示：

1 <= sentence.length <= 500
sentence 仅由大小写英文字母和空格组成
sentence 中的单词由单个空格进行分隔
不含任何前导或尾随空格

class Solution {
    public boolean isCircularSentence(String sentence) {
    }
}

分析与题解

---

• 暴力法(分割遍历法)

  又是一道简单的每日一题, 基本上一次遍历即可. 这种题的暴力方案则是根据空格分割成多个单词判断每个单词是否满足题意.

  • 如果只有一个单词,那么需要判断单词的首字母和结尾字母是否一致,不一致则返回false.

  • 如果是多个单词,那需要判断每一个单词的首字母和上一个单词的结尾字母是否一致,并且如果是最后一个单词,则需要判断其结尾字母与首个单词的开头字母是否一致.

  所以整体的解题方案如下所示.

  class Solution {
      public boolean isCircularSentence(String sentence) {
          String[] words = sentence.split(" ");
          Character firstWord = words[0].charAt(0);
          Character endWord = words[0].charAt(words[0].length() - 1);
          Character startWord;
          if (words.length == 1) {
              // 只有一个单词 特殊处理
              if (endWord != firstWord) {
                  return false;
              }
          } else {
              for (int i = 1; i < words.length; i++) {
                  startWord = words[i].charAt(0);
                  // 判断头部
                  if (startWord != endWord) {
                      return false;
                  }
                  endWord = words[i].charAt(words[i].length() - 1);
                  if (i == words.length - 1) {
                      if (endWord != firstWord) {
                          return false;
                      }
                  }
              }
          }
          return true;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 其中 n 为 sentence 的长度。
  • 空间复杂度: O(1).

  结果如下所示.

  

• 官方直接遍历法

  官方的解题思路是不进行单词分割,直接进行遍历, 需要判断以下两种情况即可完成整体题目.

  • 判断整个字符串的收尾字母是否满足相等条件.

  • 当下标为index子串为空格时, 判断 index - 1 和 index + 1 是否相等.

  class Solution {
      public boolean isCircularSentence(String sentence) {
          if (sentence.charAt(0) != sentence.charAt(sentence.length() - 1)) {
              return false;
          }
          for (int i = 0; i < sentence.length(); i++) {
              if (sentence.charAt(i) == ' ' && sentence.charAt(i -1) != sentence.charAt(i + 1)) {
                  return false;
              }
          }
          return true;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 其中 n 为 sentence 的长度。
  • 空间复杂度: O(1).

  结果如下所示.