Разбор задачи 5. Longest Palindromic Substring LeetCode.com

Самая длинная палиндромная подстрока

Учитывая строку s, вернуть самую длинную 

палиндромный

подстрокав s.

Пример 1:

Ввод: s = "babad"
 Вывод: "bab"
 Объяснение: "aba" также является допустимым ответом.

Пример 2:

Ввод: s = "cbbd"
 Вывод: "bb"

Ограничения:
1 <= s.length <= 1000
sсостоят только из цифр и английских букв.

Для решения данной задачи мы можем использовать алгоритм динамического программирования, который будет сохранять информацию о том, является ли подстрока палиндромной или нет. Мы будем использовать таблицу dp[i][j], которая будет иметь значение True, если подстрока s[i:j+1] является палиндромной, и False в противном случае.

Алгоритм:

1. Инициализируем таблицу dp[i][i] = True для всех i, так как одиночная буква всегда является палиндромом.
2. Инициализируем переменные start и max_len соответственно равными 0 и 1. start будет хранить индекс начала самой длинной палиндромной подстроки, а max_len — ее длину.
3. Мы будем перебирать подстроки длины 2 и более, начиная с самых коротких, и заполнять таблицу dp. Для каждой подстроки s[i:j+1] проверяем, является ли она палиндромом, используя значение dp[i+1][j-1] (если оно уже вычислено). Если s[i] == s[j] и dp[i+1][j-1] == True, то подстрока s[i:j+1] тоже является палиндромом, и мы устанавливаем dp[i][j] = True.
4. Если мы находим палиндромную подстроку большей длины, чем текущая самая длинная, то обновляем значения start и max_len.
5. Возвращаем подстроку s[start:start+max_len].

Решение задачи «Самая длинная палиндромная подстрока» пример кода на Python

class Solution(object):
    def longestPalindrome(self, s):    
        # длина строки
        n = len(s)  
        # двумерный массив для хранения информации о палиндромах
        dp = [[False] * n for _ in range(n)]  
        
        # инициализация массива палиндромов для односимвольных подстрок
        for i in range(n):
            dp[i][i] = True
        
        # начальный индекс подстроки-палиндрома	
        start = 0  
        # максимальная длина подстроки-палиндрома
        max_len = 1  
        
        # перебор всех подстрок длины 2 и более
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i + l - 1
                # если символы на концах подстроки совпадают и внутри тоже палиндром,
                # то подстрока также является палиндромом
                if s[i] == s[j] and (l == 2 or dp[i+1][j-1]):
                    dp[i][j] = True
                    # если новый палиндром длиннее предыдущего, то обновляем максимальную длину и начальный индекс
                    if l > max_len:
                        start = i
                        max_len = l
        
        return s[start:start+max_len]  # возвращаем найденную подстроку-палиндром

Решение задачи «Самая длинная палиндромная подстрока» пример кода на Java

class Solution {
    public String longestPalindrome(String s) {
        // длина строки
        int n = s.length(); 
        // двумерный массив для хранения информации о палиндромах
        boolean[][] dp = new boolean[n][n];  
        // начальный индекс подстроки-палиндрома и максимальная длина
        int start = 0, maxLen = 1;  
        
        // инициализация массива палиндромов для односимвольных подстрок
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // перебор всех подстрок длины 2 и более
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                // если символы на концах подстроки совпадают и внутри тоже палиндром,
                // то подстрока также является палиндромом
                if (s.charAt(i) == s.charAt(j)) {
                    // проверяем, является ли s[i:j+1] палиндромом
                    if (len == 2 || dp[i+1][j-1]) {
                        dp[i][j] = true;
                        // если новый палиндром длиннее предыдущего, то обновляем максимальную длину и начальный индекс
                        if (len > maxLen) {
                            start = i;
                            maxLen = len;
                        }
                    }
                }
            }
        }

        // возвращаем найденную подстроку-палиндром
        return s.substring(start, start + maxLen);  

    }
}

Решение задачи «Самая длинная палиндромная подстрока» пример кода на C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        // dp-таблица для хранения результатов подзадач
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // начальная позиция и длина самого длинного палиндрома
        int start = 0, maxLen = 1;

        // Одиночные буквы всегда являются палиндромами
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // Проверяем подстроки длины 2 и более
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    // Подстрока s[i:j+1] является палиндромом, если s[i+1:j-1] - палиндром и s[i] == s[j]
                    if (len == 2 || dp[i+1][j-1]) {
                        dp[i][j] = true;
                        if (len > maxLen) {
                            start = i;
                            maxLen = len;
                        }
                    }
                }
            }
        }

        // возвращаем самый длинный палиндром
        return s.substr(start, maxLen);

    }
};

Решение задачи «Самая длинная палиндромная подстрока» пример кода на JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  // получаем длину входной строки
  const n = s.length;
  // создаем двумерный массив для заполнения динамической таблицы
  const dp = new Array(n).fill().map(() => new Array(n).fill(false));
  // переменная для хранения начального индекса самой длинной подстроки-палиндрома
  let start = 0;
  // переменная для хранения длины самой длинной подстроки-палиндрома
  let maxLen = 1;

  // Инициализация динамической таблицы для одиночных символов
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // Проверяем подстроки длиной 2 и больше
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      // определяем конечный индекс подстроки
	  const j = i + len - 1;
	  // если первый и последний символы одинаковы
      if (s[i] === s[j]) {
        // если подстрока внутри является палиндромом
		if (len === 2 || dp[i+1][j-1]) {
          // помечаем подстроку i:j как палиндром
		  dp[i][j] = true;
          // если длина подстроки i:j больше текущей максимальной длины
		  if (len > maxLen) {
            // обновляем начальный индекс самой длинной подстроки-палиндрома
			start = i;
			// обновляем длину самой длинной подстроки-палиндрома
            maxLen = len;
          }
        }
      }
    }
  }

  // возвращаем самую длинную подстроку-палиндром
  return s.substring(start, start + maxLen);

};

Решение задачи «Самая длинная палиндромная подстрока» пример кода на C#

public class Solution {
    public string LongestPalindrome(string s) {
		// длина строки
        int n = s.Length; 
		// создание таблицы DP
        bool[,] dp = new bool[n, n]; 
		// начальный индекс палиндрома
        int start = 0;
		// максимальная длина палиндрома		
        int maxLen = 1; 

        // Инициализация таблицы DP для одиночных символов
        for (int i = 0; i < n; i++) {
            dp[i, i] = true;
        }

        // Проверка подстрок длиной от 2 и более
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
				// если символы равны
                if (s[i] == s[j]) { 
                    // если подстрока внутри является палиндромом
					if (len == 2 || dp[i+1, j-1]) { 
                        dp[i, j] = true;
                        // если текущий палиндром больше предыдущего
						if (len > maxLen) { 
                            start = i;
                            maxLen = len;
                        }
                    }
                }
            }
        }

        // возвращаем самый длинный палиндром
		return s.Substring(start, maxLen); 
    }
}