Teaching Kids Programming – Check if a String is Prefix/Suffix in Python (Two Pointer Algorithm)


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) —

GD Star Rating
loading...
449 words
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?

The Permanent URL is: Teaching Kids Programming – Check if a String is Prefix/Suffix in Python (Two Pointer Algorithm)

Leave a Reply