FilesExpand file tree

master

/

[1143]最长公共子序列.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

39 lines (30 loc) · 871 Bytes

master

/

[1143]最长公共子序列.java

Copy path

Top

File metadata and controls

• Code
• Blame

39 lines (30 loc) · 871 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)

class Solution {

int[][] memo;

public int longestCommonSubsequence(String text1, String text2) {

memo = new int[text1.length()][text2.length()];

for (int[] row : memo) {

Arrays.fill(row, -1);

}

return dp(text1, 0, text2, 0);

}

// 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度

int dp(String s1, int i, String s2, int j) {

//base case

if (i == s1.length() || j == s2.length()) {

return 0;

}

if (memo[i][j] != -1) {

return memo[i][j];

}

if (s1.charAt(i) == s2.charAt(j)) {

memo[i][j] = 1 + dp(s1, i + 1, s2, j + 1);

return memo[i][j];

} else {

memo[i][j] = Math.max(dp(s1, i, s2, j + 1), dp(s1, i + 1, s2, j));

return memo[i][j];

}

}

}

//leetcode submit region end(Prohibit modification and deletion)