算法题/字符串：最长公共子序列

题目

给定两个字符串s1和s2,找到在两个字符串中常见的最长子序列的长度。 子序列是一个序列，可以从另一个序列派生，删除一些元素，而不更改其余元素的顺序。

输入：s1="abdca" s2="cbda"
输出：3
解释：最长公共子序列是"bda"

题解

基础解法

Java

class LCS {

  public int findLCSLength(String s1, String s2) {
      return findLCSLengthRecursive(s1, s2, 0, 0);
  }

  private int findLCSLengthRecursive(String s1, String s2, int i1, int i2) {
    if(i1 == s1.length() || i2 == s2.length())
      return 0;

    if(s1.charAt(i1) == s2.charAt(i2))
      return 1 + findLCSLengthRecursive(s1, s2, i1+1, i2+1);//最长公共子串这里不能直接返回

    int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1);
    int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2);

    return Math.max(c1, c2);//公共序列最大值都是存在c1或c2里面返回的
  }

  public static void main(String[] args) {
    LCS lcs = new LCS();
    System.out.println(lcs.findLCSLength("abdca", "cbda"));
    System.out.println(lcs.findLCSLength("passport", "ppsspt"));
  }
}

JavaScript

class LCS {
  findLCSLength(s1, s2) {
    return this.findLCSLengthRecursive(s1, s2, 0, 0);
  }

  findLCSLengthRecursive(s1, s2, i1, i2) {
    if (i1 === s1.length || i2 === s2.length)
      return 0;

    if (s1.charAt(i1) === s2.charAt(i2))
      return 1 + this.findLCSLengthRecursive(s1, s2, i1 + 1, i2 + 1);

    const c1 = this.findLCSLengthRecursive(s1, s2, i1, i2 + 1);
    const c2 = this.findLCSLengthRecursive(s1, s2, i1 + 1, i2);

    return Math.max(c1, c2);
  }
}

const lcs = new LCS();
console.log(lcs.findLCSLength("abdca", "cbda"));
console.log(lcs.findLCSLength("passport", "ppsspt"));

Python

class LCS:
  def findLCSLength(self, s1, s2):
    return self.findLCSLengthRecursive(s1, s2, 0, 0)

  def findLCSLengthRecursive(self, s1, s2, i1, i2):
    if i1 == len(s1) or i2 == len(s2):
      return 0

    if s1[i1] == s2[i2]:
      return 1 + self.findLCSLengthRecursive(s1, s2, i1 + 1, i2 + 1)

    c1 = self.findLCSLengthRecursive(s1, s2, i1, i2 + 1)
    c2 = self.findLCSLengthRecursive(s1, s2, i1 + 1, i2)

    return max(c1, c2)

lcs = LCS()
print(lcs.findLCSLength("abdca", "cbda"))
print(lcs.findLCSLength("passport", "ppsspt"))

Go

package main

import "fmt"

type LCS struct{}

func (lcs LCS) findLCSLength(s1 string, s2 string) int {
	return lcs.findLCSLengthRecursive(s1, s2, 0, 0)
}

func (lcs LCS) findLCSLengthRecursive(s1 string, s2 string, i1 int, i2 int) int {
	if i1 == len(s1) || i2 == len(s2) {
		return 0
	}

	if s1[i1] == s2[i2] {
		return 1 + lcs.findLCSLengthRecursive(s1, s2, i1+1, i2+1)
	}

	c1 := lcs.findLCSLengthRecursive(s1, s2, i1, i2+1)
	c2 := lcs.findLCSLengthRecursive(s1, s2, i1+1, i2)

	if c1 > c2 {
		return c1
	}
	return c2
}

func main() {
	lcs := LCS{}
	fmt.Println(lcs.findLCSLength("abdca", "cbda"))
	fmt.Println(lcs.findLCSLength("passport", "ppsspt"))
}

自顶向下(备忘录)

Java

class LCS {

  public int findLCSLength(String s1, String s2) {
    Integer[][] dp = new Integer[s1.length()][s2.length()];
    return findLCSLengthRecursive(dp, s1, s2, 0, 0);
  }

  private int findLCSLengthRecursive(Integer[][] dp, String s1, String s2, int i1, int i2) {
    if (i1 == s1.length() || i2 == s2.length())
      return 0;

    if (dp[i1][i2] == null) {
      if (s1.charAt(i1) == s2.charAt(i2))
        dp[i1][i2] = 1 + findLCSLengthRecursive(dp, s1, s2, i1 + 1, i2 + 1);
      else {
        int c1 = findLCSLengthRecursive(dp, s1, s2, i1, i2 + 1);
        int c2 = findLCSLengthRecursive(dp, s1, s2, i1 + 1, i2);
        dp[i1][i2] = Math.max(c1, c2);
      }
    }

    return dp[i1][i2];
  }

  public static void main(String[] args) {
    LCS lcs = new LCS();
    System.out.println(lcs.findLCSLength("abdca", "cbda"));
    System.out.println(lcs.findLCSLength("passport", "ppsspt"));
  }
}

JavaScript

class LCS {
  findLCSLength(s1, s2) {
    const dp = Array.from({ length: s1.length }, () => Array(s2.length).fill(null));
    return this.findLCSLengthRecursive(dp, s1, s2, 0, 0);
  }

  findLCSLengthRecursive(dp, s1, s2, i1, i2) {
    if (i1 === s1.length || i2 === s2.length)
      return 0;

    if (dp[i1][i2] === null) {
      if (s1.charAt(i1) === s2.charAt(i2))
        dp[i1][i2] = 1 + this.findLCSLengthRecursive(dp, s1, s2, i1 + 1, i2 + 1);
      else {
        const c1 = this.findLCSLengthRecursive(dp, s1, s2, i1, i2 + 1);
        const c2 = this.findLCSLengthRecursive(dp, s1, s2, i1 + 1, i2);
        dp[i1][i2] = Math.max(c1, c2);
      }
    }

    return dp[i1][i2];
  }
}

const lcs = new LCS();
console.log(lcs.findLCSLength("abdca", "cbda"));
console.log(lcs.findLCSLength("passport", "ppsspt"));

Python

class LCS:
  def findLCSLength(self, s1, s2):
    dp = [[None] * len(s2) for _ in range(len(s1))]
    return self.findLCSLengthRecursive(dp, s1, s2, 0, 0)

  def findLCSLengthRecursive(self, dp, s1, s2, i1, i2):
    if i1 == len(s1) or i2 == len(s2):
      return 0

    if dp[i1][i2] is None:
      if s1[i1] == s2[i2]:
        dp[i1][i2] = 1 + self.findLCSLengthRecursive(dp, s1, s2, i1 + 1, i2 + 1)
      else:
        c1 = self.findLCSLengthRecursive(dp, s1, s2, i1, i2 + 1)
        c2 = self.findLCSLengthRecursive(dp, s1, s2, i1 + 1, i2)
        dp[i1][i2] = max(c1, c2)

    return dp[i1][i2]

lcs = LCS()
print(lcs.findLCSLength("abdca", "cbda"))
print(lcs.findLCSLength("passport", "ppsspt"))

Go

package main

import (
	"fmt"
)

type LCS struct{}

func (lcs LCS) findLCSLength(s1, s2 string) int {
	dp := make([][]int, len(s1))
	for i := range dp {
		dp[i] = make([]int, len(s2))
	}
	return lcs.findLCSLengthRecursive(dp, s1, s2, 0, 0)
}

func (lcs LCS) findLCSLengthRecursive(dp [][]int, s1, s2 string, i1, i2 int) int {
	if i1 == len(s1) || i2 == len(s2) {
		return 0
	}

	if dp[i1][i2] == 0 {
		if s1[i1] == s2[i2] {
			dp[i1][i2] = 1 + lcs.findLCSLengthRecursive(dp, s1, s2, i1+1, i2+1)
		} else {
			c1 := lcs.findLCSLengthRecursive(dp, s1, s2, i1, i2+1)
			c2 := lcs.findLCSLengthRecursive(dp, s1, s2, i1+1, i2)
			dp[i1][i2] = max(c1, c2)
		}
	}

	return dp[i1][i2]
}

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

func main() {
	lcs := LCS{}
	fmt.Println(lcs.findLCSLength("abdca", "cbda"))
	fmt.Println(lcs.findLCSLength("passport", "ppsspt"))
}

自底向上

Java

class LCS {

  public int findLCSLength(String s1, String s2) {
    int[][] dp = new int[s1.length()+1][s2.length()+1];
    int maxLength = 0;
    for(int i=1; i <= s1.length(); i++) {
      for(int j=1; j <= s2.length(); j++) {
        if(s1.charAt(i-1) == s2.charAt(j-1))
          dp[i][j] = 1 + dp[i-1][j-1];
        else
          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        
        maxLength = Math.max(maxLength, dp[i][j]);
      }
    }
    return maxLength;
  }

  public static void main(String[] args) {
    LCS lcs = new LCS();
    System.out.println(lcs.findLCSLength("abdca", "cbda"));
    System.out.println(lcs.findLCSLength("passport", "ppsspt"));
  }
}

JavaScript

class LCS {
  findLCSLength(s1, s2) {
    const dp = Array(s1.length + 1)
      .fill(0)
      .map(() => Array(s2.length + 1).fill(0));
    let maxLength = 0;
    for (let i = 1; i <= s1.length; i++) {
      for (let j = 1; j <= s2.length; j++) {
        if (s1.charAt(i - 1) === s2.charAt(j - 1))
          dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

        maxLength = Math.max(maxLength, dp[i][j]);
      }
    }
    return maxLength;
  }
}

const lcs = new LCS();
console.log(lcs.findLCSLength("abdca", "cbda"));
console.log(lcs.findLCSLength("passport", "ppsspt"));

Python

class LCS:
    def findLCSLength(self, s1, s2):
        dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        maxLength = 0
        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                
                maxLength = max(maxLength, dp[i][j])
        return maxLength

lcs = LCS()
print(lcs.findLCSLength("abdca", "cbda"))
print(lcs.findLCSLength("passport", "ppsspt"))

Go

package main

import (
	"fmt"
)

type LCS struct{}

func (lcs *LCS) findLCSLength(s1 string, s2 string) int {
	dp := make([][]int, len(s1)+1)
	for i := range dp {
		dp[i] = make([]int, len(s2)+1)
	}
	maxLength := 0
	for i := 1; i <= len(s1); i++ {
		for j := 1; j <= len(s2); j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = 1 + dp[i-1][j-1]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
			maxLength = max(maxLength, dp[i][j])
		}
	}
	return maxLength
}

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

func main() {
	lcs := LCS{}
	fmt.Println(lcs.findLCSLength("abdca", "cbda"))
	fmt.Println(lcs.findLCSLength("passport", "ppsspt"))
}