3.4. Dynamic Programming Approach

Try these first

1. 1.

   What is a subword?

   Hint

   Think about how you can take parts of a word

2. 2.

   What is the time complexity of the brute-force algorithm for finding longest common subwords?

   Hint

   Consider how many comparisons you are making.

3. 3.

   What is the focus of the longest common subword problem?

   • Finding the subword itself
   • Determining the length of the longest subword
   • Identifying mismatched characters

   Hint

   Remember that we start by calculating length before deriving the subword.

4. 4.

   True or False: The brute-force algorithm is the most efficient method for finding the longest common subword.

   • True
   • False

   Hint

   Consider the time complexity of brute-force versus dynamic programming.

5. 5.

   Given the strings 'abcdef' and 'zabcyfd', what is the length of the longest common subword?

   Hint

   Consider breaking down each string and checking for the longest matching segment.

6. 6.

   Implement a table to compute the longest common subword length between 'hello' and 'world'. Analyze and explain your results.

   Hint

   Map the characters in a grid to visualize matches.