检查字符串中的单词是否包含回文

Question

我想查找一个字符串是否包含回文词。例如，

hellosannasmith

包含回文单词，应返回

sannas

，但是

givemefood

应返回

none

。我首先尝试通过 2 个 for 循环，然后我开始思考为什么不使用 while 循环，但在开始使用 while 循环路线之前，我想看看是否可以先在 2 个 for 循环中完成。

我设法将

san

放入新的回文字符串变量中，但我不确定这里还遗漏或忽略了什么。任何帮助将不胜感激。

function SearchingChallenge(str) {
  var palindromeStr = "";

  for (var i = 0; i < str.length / 2; i++) {
    for (var j = str.length - 1; str.length / 2 < j; j--) {
      if (str[i + 1] == str[j - 1] && str[i] == str[j]) {
        palindromeStr += str[i];
      }
    }
  }

  if (palindromeStr == "") {
    return "none";
  }

  return palindromeStr;
}

console.log(SearchingChallenge('hellosannasmith'));
console.log(SearchingChallenge('givemefood'));

Answer 1

• 你可以定义一个包含所有单词的

  Set()

  ，然后使用动态规划来找到最长的回文。

• 您还可以添加一些条件以在集合中找到回文后返回回文。 （从问题中尚不清楚）。

const words = new Set(["hello", "sannas", "smith", "give", "me", "food"]);

function SearchingChallenge(str) {
  const n = str.length;
  if (n === 0) return "none";

  let res = "";
  const dp = Array.from({ length: n }, () => Array(n).fill(false));

  for (let len = 1; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (len === 1) {
        dp[i][j] = true;
      } else if (len === 2) {
        dp[i][j] = str[i] === str[j];
      } else {
        dp[i][j] = str[i] === str[j] && dp[i + 1][j - 1];
      }
      if (dp[i][j] && len > res.length) {
        res = str.slice(i, j + 1);
      }
    }
  }

  return words.has(res) ? res : "none";
}

console.log(SearchingChallenge("hellosannasmith"));
console.log(SearchingChallenge("givemefood"));