Unit 10 Session 2 (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Explanation: "ABC" is the largest string that divides both "ABCABC" and "ABC".
HAPPY CASE 2
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Explanation: "AB" is the largest string that divides both "ABABAB" and "ABAB".
EDGE CASE
Input: str1 = "LEET", str2 = "CODE"
Output: "
Explanation: There is no common divisor string that divides both "LEET" and "CODE".
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For String problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use the GCD of the lengths of the two strings to find the largest possible divisor string. Check if this string divides both str1
and str2
.
1) Define a helper function `is_divisible(s, t)` that checks if string `t` divides string `s`.
2) Find the GCD of the lengths of `str1` and `str2`.
3) Use the GCD length to extract a candidate substring from `str1`.
4) Check if this candidate substring divides both `str1` and `str2`.
5) Return the candidate substring if it divides both strings; otherwise, return an empty string.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def gcd_of_strings(str1, str2):
def is_divisible(s, t):
if len(s) % len(t) != 0:
return False
repeat = len(s) // len(t)
return t * repeat == s
def gcd(a, b):
while b:
a, b = b, a % b
return a
gcd_length = gcd(len(str1), len(str2))
candidate = str1[:gcd_length]
if is_divisible(str1, candidate) and is_divisible(str2, candidate):
return candidate
return "
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of the shorter string.
O(N)
because we need to check divisibility and find the GCD of the lengths.O(1)
because we only use a constant amount of extra space.