4.3.1. Case When Characters Match

Try these first

1. 1.

   Define what a subsequence is.

   Hint

   Think about the letters in a word.

2. 2.

   What does LCS stand for?

   Hint

   It's a term frequently used in programming and data analysis.

3. 3.

   What is the time complexity of the naive LCS solution?

   • O(m*n)
   • O(m+n)
   • O(m^2+n^2)

   Hint

   Think about how many combinations you’re checking.

4. 4.

   Is a subsequence required to maintain the order of characters?

   • True
   • False

   Hint

   Reflect on how you can form sequences from words.

5. 5.

   Given two strings 'ABC' and 'AC', determine the LCS and demonstrate the steps taken during the computation.

   Hint

   Map out how characters align in the strings.

6. 6.

   Implement a simple algorithm using dynamic programming to compute the LCS for two strings provided in an input.

   Hint

   Visualize filling the matrix as you compare each character.