Teaching Kids Programming: Videos on Data Structures and Algorithms
Prefix Algorithm using Two Pointer in Python
In Python, we can use the startswith function to check if a string is a prefix of another string. This is case-sensitive checks:
1 2 | "abcdef".startswith("abc") # True "abcdef".startswith("ABC") # False |
"abcdef".startswith("abc") # True "abcdef".startswith("ABC") # False
We can also use find function which returns the first occurence index location (-1 if not found) of a substring that appears in the origin string. Then we just have to check if the first occurence index is zero:
1 2 | "abcdef".find("abc") == 0 # True "Aabcdef".find("abc") == 0 # False |
"abcdef".find("abc") == 0 # True "Aabcdef".find("abc") == 0 # False
We can use the two pointer algorithm to do character by character checking. If the length of the prefix string is longer than the given string, we can immediately exit the function and returns the False as a prefix cannot be longer than the original string.
1 2 3 4 5 6 7 8 9 10 | def isPrefix(p, s): if len(p) > len(s): return False i = 0 n = len(p) while i < n: if p[i] != s[i]: return False i += 1 return True |
def isPrefix(p, s): if len(p) > len(s): return False i = 0 n = len(p) while i < n: if p[i] != s[i]: return False i += 1 return True
The time complexity is O(N) where N is the number of characters in the prefix string.
Suffix Algorithm using Two Pointer in Python
Similar to Prefix, but we can do suffix checks from the ends:
1 2 3 4 5 6 7 8 9 10 11 | def isSuffix(p, s): if len(p) > len(s): return False s = len(s) - 1 i = len(p) - 1 while i >= 0: if p[i] != s[j]: return False i -= 1 j -= 1 return True |
def isSuffix(p, s): if len(p) > len(s): return False s = len(s) - 1 i = len(p) - 1 while i >= 0: if p[i] != s[j]: return False i -= 1 j -= 1 return True
Given a prefix function, we can reverse both strings to check the suffix, alternatively, we can call suffix to check prefix. For example:
1 2 | def isPrefix(p, s): return isSuffix(p[::-1], s[::-1]) |
def isPrefix(p, s): return isSuffix(p[::-1], s[::-1])
If you are given suffix function:
1 2 | def isSuffix(p, s): return isPrefix(p[::-1], s[::-1]) |
def isSuffix(p, s): return isPrefix(p[::-1], s[::-1])
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - How to Draw a Star using Turtle Graphics? (Math, Shapes, Geometry)
Next Post: Teaching Kids Programming - How to Draw a Chess Board using Python and Turtle Graphics?