算法题/序列：最长回文子串

题目

给定一个字符串,找到它最长的回文子字符串(LPS)的长度。在一个回文字符串中,从字符串的末尾向左读和从字符串的开头向右读是一样的。

示例：

输入："abdbca"
输出：3
解释：最长回文子串是"bdb"

题解

暴力求解

Java

class LPS {

  public int findLPSLength(String st) {
    return findLPSLengthRecursive(st, 0, st.length() - 1);
  }

  private int findLPSLengthRecursive(String st, int startIndex, int endIndex) {
    if (startIndex > endIndex)
      return 0;

    // 每一个只有一个字符的字符串是一个回文
    if (startIndex == endIndex)
      return 1;

    // case 1: 开头和结尾的元素相同
    if (st.charAt(startIndex) == st.charAt(endIndex)) {
      int remainingLength = endIndex - startIndex - 1;
      // 检查剩余的字符串是否是回文子串
      if (remainingLength == findLPSLengthRecursive(st, startIndex + 1, endIndex - 1))
        return remainingLength + 2;
    }

    // case 2: 略过开头或者结尾的一个元素
    int c1 = findLPSLengthRecursive(st, startIndex + 1, endIndex);
    int c2 = findLPSLengthRecursive(st, startIndex, endIndex - 1);
    return Math.max(c1, c2);
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cddpd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

JavaScript

class LPS {
  findLPSLength(st) {
    return this.findLPSLengthRecursive(st, 0, st.length - 1);
  }

  findLPSLengthRecursive(st, startIndex, endIndex) {
    if (startIndex > endIndex) return 0;

    if (startIndex === endIndex) return 1;

    if (st.charAt(startIndex) === st.charAt(endIndex)) {
      const remainingLength = endIndex - startIndex - 1;
      if (
        remainingLength ===
        this.findLPSLengthRecursive(st, startIndex + 1, endIndex - 1)
      )
        return remainingLength + 2;
    }

    const c1 = this.findLPSLengthRecursive(st, startIndex + 1, endIndex);
    const c2 = this.findLPSLengthRecursive(st, startIndex, endIndex - 1);
    return Math.max(c1, c2);
  }
}

const lps = new LPS();
console.log(lps.findLPSLength("abdbca"));
console.log(lps.findLPSLength("cddpd"));
console.log(lps.findLPSLength("pqr"));

Python

class LPS:
    def findLPSLength(self, st):
        return self.findLPSLengthRecursive(st, 0, len(st) - 1)

    def findLPSLengthRecursive(self, st, startIndex, endIndex):
        if startIndex > endIndex:
            return 0

        if startIndex == endIndex:
            return 1

        if st[startIndex] == st[endIndex]:
            remainingLength = endIndex - startIndex - 1
            if remainingLength == self.findLPSLengthRecursive(st, startIndex + 1, endIndex - 1):
                return remainingLength + 2

        c1 = self.findLPSLengthRecursive(st, startIndex + 1, endIndex)
        c2 = self.findLPSLengthRecursive(st, startIndex, endIndex - 1)
        return max(c1, c2)


lps = LPS()
print(lps.findLPSLength("abdbca"))
print(lps.findLPSLength("cddpd"))
print(lps.findLPSLength("pqr"))

Go

package main

import "fmt"

type LPS struct{}

func (lps *LPS) findLPSLength(st string) int {
	return lps.findLPSLengthRecursive(st, 0, len(st)-1)
}

func (lps *LPS) findLPSLengthRecursive(st string, startIndex int, endIndex int) int {
	if startIndex > endIndex {
		return 0
	}

	if startIndex == endIndex {
		return 1
	}

	if st[startIndex] == st[endIndex] {
		remainingLength := endIndex - startIndex - 1
		if remainingLength == lps.findLPSLengthRecursive(st, startIndex+1, endIndex-1) {
			return remainingLength + 2
		}
	}

	c1 := lps.findLPSLengthRecursive(st, startIndex+1, endIndex)
	c2 := lps.findLPSLengthRecursive(st, startIndex, endIndex-1)
	if c1 > c2 {
		return c1
	}
	return c2
}

func main() {
	lps := LPS{}
	fmt.Println(lps.findLPSLength("abdbca"))
	fmt.Println(lps.findLPSLength("cddpd"))
	fmt.Println(lps.findLPSLength("pqr"))
}

自顶向下(备忘录)

Java

class LPS {

  public int findLPSLength(String st) {
    Integer[][] dp = new Integer[st.length()][st.length()];
    return findLPSLengthRecursive(dp, st, 0, st.length() - 1);
  }

  private int findLPSLengthRecursive(Integer[][] dp, String st, int startIndex, int endIndex) {
    if (startIndex > endIndex)
      return 0;

    // 每一个只有一个字符的字符串是一个回文
    if (startIndex == endIndex)
      return 1;

    if (dp[startIndex][endIndex] == null) {
      // case 1: 开头和结尾的元素相同
      if (st.charAt(startIndex) == st.charAt(endIndex)) {
        int remainingLength = endIndex - startIndex - 1;
        // 检查剩余的字符串是否也是一个回文
        if (remainingLength == findLPSLengthRecursive(dp, st, startIndex + 1, endIndex - 1)) {
          dp[startIndex][endIndex] = remainingLength + 2;
          return dp[startIndex][endIndex];
        }
      }

      // case 2: 从开头或者结尾跳过一个字符
      int c1 = findLPSLengthRecursive(dp, st, startIndex + 1, endIndex);
      int c2 = findLPSLengthRecursive(dp, st, startIndex, endIndex - 1);
      dp[startIndex][endIndex] = Math.max(c1, c2);
    }

    return dp[startIndex][endIndex];
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cddpd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

JavaScript

class LPS {
  findLPSLength(st) {
    const dp = new Array(st.length).fill(null).map(() => new Array(st.length).fill(null));
    return this.findLPSLengthRecursive(dp, st, 0, st.length - 1);
  }

  findLPSLengthRecursive(dp, st, startIndex, endIndex) {
    if (startIndex > endIndex)
      return 0;

    if (startIndex === endIndex)
      return 1;

    if (dp[startIndex][endIndex] === null) {
      if (st.charAt(startIndex) === st.charAt(endIndex)) {
        const remainingLength = endIndex - startIndex - 1;
        if (remainingLength === this.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex - 1)) {
          dp[startIndex][endIndex] = remainingLength + 2;
          return dp[startIndex][endIndex];
        }
      }

      const c1 = this.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex);
      const c2 = this.findLPSLengthRecursive(dp, st, startIndex, endIndex - 1);
      dp[startIndex][endIndex] = Math.max(c1, c2);
    }

    return dp[startIndex][endIndex];
  }
}

const lps = new LPS();
console.log(lps.findLPSLength("abdbca"));
console.log(lps.findLPSLength("cddpd"));
console.log(lps.findLPSLength("pqr"));

Python

class LPS:
  def findLPSLength(self, st):
    dp = [[None] * len(st) for _ in range(len(st))]
    return self.findLPSLengthRecursive(dp, st, 0, len(st) - 1)

  def findLPSLengthRecursive(self, dp, st, startIndex, endIndex):
    if startIndex > endIndex:
      return 0

    if startIndex == endIndex:
      return 1

    if dp[startIndex][endIndex] is None:
      if st[startIndex] == st[endIndex]:
        remainingLength = endIndex - startIndex - 1
        if remainingLength == self.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex - 1):
          dp[startIndex][endIndex] = remainingLength + 2
          return dp[startIndex][endIndex]

      c1 = self.findLPSLengthRecursive(dp, st, startIndex + 1, endIndex)
      c2 = self.findLPSLengthRecursive(dp, st, startIndex, endIndex - 1)
      dp[startIndex][endIndex] = max(c1, c2)

    return dp[startIndex][endIndex]

lps = LPS()
print(lps.findLPSLength("abdbca"))
print(lps.findLPSLength("cddpd"))
print(lps.findLPSLength("pqr"))

Go

package main

import "fmt"

type LPS struct{}

func (lps *LPS) findLPSLength(st string) int {
	dp := make([][]int, len(st))
	for i := range dp {
		dp[i] = make([]int, len(st))
	}
	return lps.findLPSLengthRecursive(dp, st, 0, len(st)-1)
}

func (lps *LPS) findLPSLengthRecursive(dp [][]int, st string, startIndex, endIndex int) int {
	if startIndex > endIndex {
		return 0
	}

	if startIndex == endIndex {
		return 1
	}

	if dp[startIndex][endIndex] == 0 {
		if st[startIndex] == st[endIndex] {
			remainingLength := endIndex - startIndex - 1
			if remainingLength == lps.findLPSLengthRecursive(dp, st, startIndex+1, endIndex-1) {
				dp[startIndex][endIndex] = remainingLength + 2
				return dp[startIndex][endIndex]
			}
		}

		c1 := lps.findLPSLengthRecursive(dp, st, startIndex+1, endIndex)
		c2 := lps.findLPSLengthRecursive(dp, st, startIndex, endIndex-1)
		dp[startIndex][endIndex] = max(c1, c2)
	}

	return dp[startIndex][endIndex]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	lps := &LPS{}
	fmt.Println(lps.findLPSLength("abdbca"))
	fmt.Println(lps.findLPSLength("cddpd"))
	fmt.Println(lps.findLPSLength("pqr"))
}

自底向上

Java

class LPS {

  public int findLPSLength(String st) {
    // 如果索引i到索引j是一个回文，则dp[i][j]是true。
    // 对于回文序列需要存储回文子序列的长度，而回文子串不用，因为回文子串的长度可以通过endIndex-startIndex+1求出
    boolean[][] dp = new boolean[st.length()][st.length()];

    // 每个只有一个字符的字符串是一个回文
    for (int i = 0; i < st.length(); i++)
      dp[i][i] = true;

    int maxLength = 1;
    for (int startIndex = st.length() - 1; startIndex >= 0; startIndex--) {
      for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {
        if (st.charAt(startIndex) == st.charAt(endIndex)) {
          // 如果它是两个字符 或者 剩余的字符串是一个回文的话
          if (endIndex - startIndex == 1 || dp[startIndex + 1][endIndex - 1]) {
            dp[startIndex][endIndex] = true;
            maxLength = Math.max(maxLength, endIndex - startIndex + 1);
          }
        }
      }
    }

    return maxLength;
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cdpdd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

JavaScript

class LPS {
  findLPSLength(st) {
    const dp = new Array(st.length);
    for (let i = 0; i < st.length; i++) {
      dp[i] = new Array(st.length).fill(false);
      dp[i][i] = true;
    }

    let maxLength = 1;
    for (let startIndex = st.length - 1; startIndex >= 0; startIndex--) {
      for (let endIndex = startIndex + 1; endIndex < st.length; endIndex++) {
        if (st.charAt(startIndex) === st.charAt(endIndex)) {
          if (endIndex - startIndex === 1 || dp[startIndex + 1][endIndex - 1]) {
            dp[startIndex][endIndex] = true;
            maxLength = Math.max(maxLength, endIndex - startIndex + 1);
          }
        }
      }
    }

    return maxLength;
  }
}

const lps = new LPS();
console.log(lps.findLPSLength("abdbca"));
console.log(lps.findLPSLength("cdpdd"));
console.log(lps.findLPSLength("pqr"));

Python

class LPS:
    def findLPSLength(self, st):
        dp = [[False] * len(st) for _ in range(len(st))]
        
        # 每个只有一个字符的字符串是一个回文
        for i in range(len(st)):
            dp[i][i] = True
        
        maxLength = 1
        for startIndex in range(len(st) - 1, -1, -1):
            for endIndex in range(startIndex + 1, len(st)):
                if st[startIndex] == st[endIndex]:
                    # 如果它是两个字符或者剩余的字符串是一个回文的话
                    if endIndex - startIndex == 1 or dp[startIndex + 1][endIndex - 1]:
                        dp[startIndex][endIndex] = True
                        maxLength = max(maxLength, endIndex - startIndex + 1)
        
        return maxLength


lps = LPS()
print(lps.findLPSLength("abdbca"))
print(lps.findLPSLength("cdpdd"))
print(lps.findLPSLength("pqr"))

Go

package main

import (
	"fmt"
)

type LPS struct{}

func (lps *LPS) findLPSLength(st string) int {
	dp := make([][]bool, len(st))
	for i := range dp {
		dp[i] = make([]bool, len(st))
		dp[i][i] = true
	}

	maxLength := 1
	for startIndex := len(st) - 1; startIndex >= 0; startIndex-- {
		for endIndex := startIndex + 1; endIndex < len(st); endIndex++ {
			if st[startIndex] == st[endIndex] {
				if endIndex-startIndex == 1 || dp[startIndex+1][endIndex-1] {
					dp[startIndex][endIndex] = true
					maxLength = max(maxLength, endIndex-startIndex+1)
				}
			}
		}
	}

	return maxLength
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	lps := LPS{}
	fmt.Println(lps.findLPSLength("abdbca"))
	fmt.Println(lps.findLPSLength("cdpdd"))
	fmt.Println(lps.findLPSLength("pqr"))
}