2108. 找出数组中的第一个回文字符串

🟢   🔖  数组 双指针 字符串  🔗 力扣 LeetCode

题目

Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]

Output: "ada"

Explanation: The first string that is palindromic is "ada".

Note that "racecar" is also palindromic, but it is not the first.

Example 2:

Input: words = ["notapalindrome","racecar"]

Output: "racecar"

Explanation: The first and only string that is palindromic is "racecar".

Example 3:

Input: words = ["def","ghi"]

Output: ""

Explanation: There are no palindromic strings, so the empty string is returned.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists only of lowercase English letters.

题目大意

给你一个字符串数组 words ，找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串，返回一个 空字符串 "" 。

回文字符串 的定义为：如果一个字符串正着读和反着读一样，那么该字符串就是一个 回文字符串 。

示例 1：

输入： words = ["abc","car","ada","racecar","cool"]

输出： "ada"

解释： 第一个回文字符串是 "ada" 。

注意，"racecar" 也是回文字符串，但它不是第一个。

示例 2：

输入： words = ["notapalindrome","racecar"]

输出： "racecar"

解释： 第一个也是唯一一个回文字符串是 "racecar" 。

示例 3：

输入： words = ["def","ghi"]

输出： ""

解释： 不存在回文字符串，所以返回一个空字符串。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成

解题思路

1. 定义回文检查函数 isPalindrome:

   • 回文字符串是指正序和反序相同的字符串。
   • 使用双指针方法从两端向中间检查：
     • 左指针从字符串开头移动 (left)。
     • 右指针从字符串末尾移动 (right)。
     • 如果对应位置的字符不相等，则不是回文，返回 false。
     • 如果指针相遇或交错，说明是回文，返回 true。

2. 遍历 words 数组:

   • 对每个字符串调用 isPalindrome 检查是否是回文。
   • 如果找到回文字符串，立即返回该字符串。

3. 返回结果:

   • 如果遍历完成后没有找到回文字符串，返回空字符串 ''。

复杂度分析

• 时间复杂度：O(n * m)，其中 words 的长度为 n，每个字符串的平均长度为 m。
  • 对每个字符串调用 isPalindrome，时间复杂度为 O(m)。
  • 遍历所有字符串，最坏情况下需要 O(n * m)。
• 空间复杂度：O(1)，使用了常数额外空间。

代码

/**
 * @param {string[]} words
 * @return {string}
 */
var firstPalindrome = function (words) {
	const isPalindrome = (str) => {
		let left = 0;
		let right = str.length - 1;
		while (left < right) {
			if (str[left] != str[right]) return false;
			left++;
			right--;
		}
		return true;
	};
	for (let word of words) {
		if (isPalindrome(word)) return word;
	}
	return '';
};

相关题目

题号	标题	题解	标签	难度	力扣
125	验证回文串	[✓]	双指针 字符串	🟢	🀄️ 🔗