educative.io

Educative

Regarding the dp array definition in LCS soution

In most of other question, i.e. LPS, the dp size was defined by the length of st.
public int findLPSLength(String st) {
Integer[][] dp = new Integer[st.length()][st.length()];

However, in this LCS solution, you used s1.length()+1, could you please help to explain? Thanks.
public int findLCSLength(String s1, String s2) {
int[][] dp = new int[s1.length()+1][s2.length()+1];

The reason why this works is because the for loops begin with I=1 and J=1, and we check the for the character at i-1 and j-1 respectively in the strings. We could have switched to 0 and used I and J directly without subtracting them.

2 Likes