Longest Common Prefix in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Common Prefix (LCP) in a list of strings?

The Longest Common Prefix is the longest starting substring that is common to all strings in the list.

beginner

How do you find the LCP by comparing characters vertically?

Check each character position across all strings. Stop when a mismatch or end of any string is found. The matched characters so far form the LCP.

intermediate

What is the time complexity of the vertical scanning method for LCP?

O(S) where S is the sum of all characters in all strings, because each character is checked at most once.

beginner

Why is it important to handle empty strings or empty list when finding LCP?

Because if the list is empty or contains empty strings, the LCP is empty. Handling these avoids errors and incorrect results.

intermediate

What is a simple Python code snippet to find the LCP using horizontal scanning?

Start with the first string as prefix. Compare prefix with each string and shorten prefix until it matches. Return prefix at the end.

What does the Longest Common Prefix represent?

A The longest substring common anywhere in all strings

B The longest substring common at the end of all strings

C The longest substring common at the start of all strings

D The shortest string in the list

The LCP is the longest starting substring shared by all strings.

If the input list is empty, what should the LCP be?

A Empty string

B None

C First string in the list

D Error

With no strings, the longest common prefix is empty.

Which approach compares characters column by column across all strings?

A Binary search

B Horizontal scanning

C Divide and conquer

D Vertical scanning

Vertical scanning checks each character position across all strings.

What happens if one string is empty in the list?

A LCP is the longest string

B LCP is empty string

C LCP is the shortest non-empty string

D LCP is the first string

An empty string means no common prefix beyond empty string.

What is the time complexity of checking all characters in all strings for LCP?

A O(S), where S is total characters

B O(N), where N is number of strings

C O(1)

D O(log N)

Each character in all strings is checked at most once, so O(S).

Explain how you would find the Longest Common Prefix in a list of strings using vertical scanning.

Think about comparing characters column by column.

Describe edge cases to consider when implementing Longest Common Prefix.

What if no strings or some strings are empty?