Function lcs

longest_common_subsequence_1143/solution.go:45–76

(text1, text2 string, text1Idx, text2Idx int, memo [][]int)

}

func lcs(text1, text2 string, text1Idx, text2Idx int, memo [][]int) int {
	// if text1 or text 2 are empty, there is no longest common substring
	if text1Idx == 0 || text2Idx == 0 {
		return 0
	}

	// Aha! Use of 2d array for memoization concept sticking for me.
	// I tried to use two different keys by my 1st and 2nd intuition.
	// Found out that the 2d array suites this need perfectly.
	// The row (text1Idx) and column (text2Idx) can be the key to the location
	// in the 2d array. This is much faster and very useful.

	//key := text1Idx * 10 + text2Idx (incorrect)
	//key := text1[0:text1Idx] + text2[0:text2Idx] (OOM on leetcode)
	if memo[text1Idx][text2Idx] != -1 {
		return memo[text1Idx][text2Idx]
	}

	// if text1 and text2 at their indices are equal, then they are
	// a part of a common subsequence
	if text1[text1Idx-1] == text2[text2Idx-1] {
		memo[text1Idx][text2Idx] = 1 + lcs(text1, text2, text1Idx-1, text2Idx-1, memo)
		return memo[text1Idx][text2Idx]
	}

	// find the max by choosing to clip off the last character
	// on (text1, not text2) and (not text1, text2)
	l1 := lcs(text1, text2, text1Idx-1, text2Idx, memo)
	l2 := lcs(text1, text2, text1Idx, text2Idx-1, memo)
	memo[text1Idx][text2Idx] = int(math.Max(float64(l1), float64(l2)))
	return memo[text1Idx][text2Idx]
}

// Note: first attempt that passed test cases in description examples.
// Isn't correct in all cases.