JavaScript의 문자열 내에서 가능한 모든 회문 하위 시퀀스 계산

회문 시퀀스:

문자열 시퀀스는 앞뒤에서 동일하게 읽는 경우 회문 시퀀스로 알려져 있습니다. 예를 들어, 'aba', 'madam, 'did'는 모두 유효한 회문 시퀀스입니다.

문자열을 첫 번째이자 유일한 인수로 취하는 JavaScript 함수를 작성해야 합니다. 입력으로 사용되는 문자열은 'a', 'b', 'c' 및 'd'로만 구성되도록 보장됩니다. 우리 함수는 문자열에 나타나는 모든 인접 또는 비연속 회문 하위 시퀀스의 수를 계산하고 반환해야 합니다.

예를 들어 -

입력 문자열이 -

const str = 'bccb';

그러면 출력은 다음과 같아야 합니다. -

const output = 6;

회문 문자열이 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'이기 때문에

예시

이에 대한 코드는 -

const str = 'bccb';
const countPalindromes = (str = '') => {
   let base = 1000000007;
   const dp = Array(str.length).fill([]);
   for (let l = 1; l <= str.length; l ++) {
      for (let i = 0; i + l - 1 < str.length; i ++) {
         let j = i + l - 1;
         if (l === 1) {
            dp[i][j] = 1;
            continue;
         }
         if (l === 2) {
            dp[i][j] = 2;
            continue;
         }
         if (str[i] === str[j]) {
            let left = i + 1, right = j - 1;
            while (left <= right && str[left] != str[i]) {
               left ++;
            }
            while (left <= right && str[right] != str[i]) {
               right --;
            }
            if (left > right) {
               dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
            }
            else if (left === right) {
               dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
            } else {
               dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
            }
         } else {
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
         }
         dp[i][j] = dp[i][j] < 0? dp[i][j] + base : dp[i][j] % base;
      }
   }
   return dp[0][str.length - 1];
};
console.log(countPalindromes(str));

출력

콘솔의 출력은 -

6