Question

2490. 回环句

English Version

题目描述

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

• 例如，"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"] 。
- leetcod_e_ 的最后一个字符和 _e_xercises 的第一个字符相等。
- exercise_s_ 的最后一个字符和 _s_ound 的第一个字符相等。
- _s_ound 的最后一个字符和 delightfu_l_ 的第一个字符相等。
- delightfu_l_ 的最后一个字符和 _l_eetcode 的第一个字符相等。
这个句子是回环句。

示例 2：

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

示例 3：

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

 

提示：

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

解法

方法一：模拟

我们将字符串按照空格分割成单词，然后判断每个单词的最后一个字符和下一个单词的第一个字符是否相等，如果不相等则返回 false，否则遍历完所有单词后返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串的长度。

class Solution:
  def isCircularSentence(self, sentence: str) -> bool:
    ss = sentence.split()
    n = len(ss)
    return all(s[-1] == ss[(i + 1) % n][0] for i, s in enumerate(ss))

class Solution {
  public boolean isCircularSentence(String sentence) {
    var ss = sentence.split(" ");
    int n = ss.length;
    for (int i = 0; i < n; ++i) {
      if (ss[i].charAt(ss[i].length() - 1) != ss[(i + 1) % n].charAt(0)) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool isCircularSentence(string sentence) {
    auto ss = split(sentence, ' ');
    int n = ss.size();
    for (int i = 0; i < n; ++i) {
      if (ss[i].back() != ss[(i + 1) % n][0]) {
        return false;
      }
    }
    return true;
  }

  vector<string> split(string& s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }
};

func isCircularSentence(sentence string) bool {
  ss := strings.Split(sentence, " ")
  n := len(ss)
  for i, s := range ss {
    if s[len(s)-1] != ss[(i+1)%n][0] {
      return false
    }
  }
  return true
}

function isCircularSentence(sentence: string): boolean {
  const ss = sentence.split(' ');
  const n = ss.length;
  for (let i = 0; i < n; ++i) {
    if (ss[i][ss[i].length - 1] !== ss[(i + 1) % n][0]) {
      return false;
    }
  }
  return true;
}

impl Solution {
  pub fn is_circular_sentence(sentence: String) -> bool {
    let ss: Vec<String> = sentence.split(' ').map(String::from).collect();
    let n = ss.len();
    for i in 0..n {
      if ss[i].as_bytes()[ss[i].len() - 1] != ss[(i + 1) % n].as_bytes()[0] {
        return false;
      }
    }
    return true;
  }
}

/**
 * @param {string} sentence
 * @return {boolean}
 */
var isCircularSentence = function (sentence) {
  const ss = sentence.split(' ');
  const n = ss.length;
  for (let i = 0; i < n; ++i) {
    if (ss[i][ss[i].length - 1] !== ss[(i + 1) % n][0]) {
      return false;
    }
  }
  return true;
};

方法二：模拟（空间优化）

我们可以先判断字符串的第一个字符和最后一个字符是否相等，如果不相等则返回 false，否则遍历字符串，如果当前字符是空格，则判断前一个字符和后一个字符是否相等，如果不相等则返回 false，否则遍历完所有字符后返回 true。

时间复杂度 $O(n)$，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$。

class Solution:
  def isCircularSentence(self, s: str) -> bool:
    return s[0] == s[-1] and all(
      c != " " or s[i - 1] == s[i + 1] for i, c in enumerate(s)
    )

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

class Solution {
public:
  bool isCircularSentence(string s) {
    int n = s.size();
    if (s[0] != s.back()) {
      return false;
    }
    for (int i = 1; i < n; ++i) {
      if (s[i] == ' ' && s[i - 1] != s[i + 1]) {
        return false;
      }
    }
    return true;
  }
};

func isCircularSentence(s string) bool {
  n := len(s)
  if s[0] != s[n-1] {
    return false
  }
  for i := 1; i < n; i++ {
    if s[i] == ' ' && s[i-1] != s[i+1] {
      return false
    }
  }
  return true
}

function isCircularSentence(s: string): boolean {
  const n = s.length;
  if (s[0] !== s[n - 1]) {
    return false;
  }
  for (let i = 1; i < n; ++i) {
    if (s[i] === ' ' && s[i - 1] !== s[i + 1]) {
      return false;
    }
  }
  return true;
}

impl Solution {
  pub fn is_circular_sentence(sentence: String) -> bool {
    let n = sentence.len();
    let chars: Vec<char> = sentence.chars().collect();

    if chars[0] != chars[n - 1] {
      return false;
    }

    for i in 1..n - 1 {
      if chars[i] == ' ' && chars[i - 1] != chars[i + 1] {
        return false;
      }
    }

    true
  }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isCircularSentence = function (s) {
  const n = s.length;
  if (s[0] !== s[n - 1]) {
    return false;
  }
  for (let i = 1; i < n; ++i) {
    if (s[i] === ' ' && s[i - 1] !== s[i + 1]) {
      return false;
    }
  }
  return true;
};