最长公共子串

题目

给定两个字符串' s1 '和' s2 '，找出两个字符串中最长的公共子字符串的长度。

输入：S1="abdca" S2="cbda"
输出：2
解释：最长公共子串是"bd"

题解

基础解法

class LCS {

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

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

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

    int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1, 0);
    int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2, 0);
	//公共序列最大值存在count,c1或c2里面返回的，（不确定：count保存的是以前的最大值）
    return Math.max(count, Math.max(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"));
  }
}

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

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

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

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

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

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

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

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

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

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

    return max(count, c1, c2)

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

package main

import "fmt"

type LCS struct{}

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

func (l *LCS) findLCSLengthRecursive(s1 string, s2 string, i1 int, i2 int, count int) int {
	if i1 == len(s1) || i2 == len(s2) {
		return count
	}

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

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

	if count > c1 && count > c2 {
		return count
	} else if c1 > count && c1 > c2 {
		return c1
	} else {
		return c2
	}
}

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

自顶向下(备忘录)

class LCS {

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

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

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

    return dp[i1][i2][count];
  }

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

class LCS {
  findLCSLength(s1, s2) {
    const maxLength = Math.min(s1.length, s2.length);
    const dp = new Array(s1.length).fill(null).map(() =>
      new Array(s2.length).fill(null).map(() => new Array(maxLength))
    );
    return this.findLCSLengthRecursive(dp, s1, s2, 0, 0, 0);
  }

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

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

    return dp[i1][i2][count];
  }
}

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

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

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

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

        return dp[i1][i2][count]


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

package main

import (
	"fmt"
)

type LCS struct{}

func (lcs LCS) findLCSLength(s1 string, s2 string) int {
	maxLength := min(len(s1), len(s2))
	dp := make([][][]int, len(s1))
	for i := 0; i < len(s1); i++ {
		dp[i] = make([][]int, len(s2))
		for j := 0; j < len(s2); j++ {
			dp[i][j] = make([]int, maxLength)
		}
	}
	return lcs.findLCSLengthRecursive(dp, s1, s2, 0, 0, 0)
}

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

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

	return dp[i1][i2][count]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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"))
}

自底向上

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];
          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"));
  }
}

class LCS {
  findLCSLength(s1, s2) {
    const dp = Array.from(Array(s1.length + 1), () => 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];
          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"));

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]
                    maxLength = max(maxLength, dp[i][j])
        return maxLength

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

package main

import "fmt"

type LCS struct{}

func (l *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]
				if dp[i][j] > maxLength {
					maxLength = dp[i][j]
				}
			}
		}
	}

	return maxLength
}

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