Check if String Follows Order of Characters Defined by a Pattern or Not | Set 2

In programming, there are often scenarios where we need to determine if a given string adheres to a specific order of characters defined by a pattern. This can be useful in various applications such as validating input formats, parsing text according to a predefined structure, etc. In this blog post, we'll explore different approaches to solve this problem, along with best practices and example usage.

Table of Content#

  1. Problem Statement
  2. Brute - Force Approach
    • Explanation
    • Implementation (Python)
    • Time and Space Complexity
  3. Hash Map Approach
    • Explanation
    • Implementation (Python)
    • Time and Space Complexity
  4. Best Practices
    • Input Validation
    • Code Readability
  5. Example Usage
  6. References

1. Problem Statement#

Given a pattern string pattern and a target string s, we need to check if the characters in s follow the order of characters in pattern. For example, if pattern = "abc" and s = "aabbcc", then s follows the pattern. But if s = "aaabb", it does not follow the pattern.

2. Brute - Force Approach#

Explanation#

The brute - force approach involves iterating through the pattern and the s string simultaneously. For each character in the pattern, we check if the corresponding characters in s match the order.

Implementation (Python)#

def follows_pattern_brute(pattern, s):
    if len(pattern) == 0 or len(s) == 0:
        return False
    i = 0
    j = 0
    while i < len(pattern) and j < len(s):
        if pattern[i] == s[j]:
            i += 1
            j += 1
        else:
            j += 1
    return i == len(pattern)

Time and Space Complexity#

  • Time Complexity: In the worst case, for each character in pattern, we may need to scan through a significant portion of s. So, the time complexity is $O(n \cdot m)$, where $n$ is the length of s and $m$ is the length of pattern.
  • Space Complexity: We are using only a few extra variables (i and j), so the space complexity is $O(1)$.

3. Hash Map Approach#

Explanation#

We can use a hash map (dictionary in Python) to map each character in the pattern to its position. Then, we iterate through the s string and check if the characters follow the order based on their mapped positions.

Implementation (Python)#

def follows_pattern_hash(pattern, s):
    if len(pattern) == 0 or len(s) == 0:
        return False
    pattern_map = {}
    for index, char in enumerate(pattern):
        pattern_map[char] = index
    pattern_index = 0
    for char in s:
        if char in pattern_map:
            if pattern_map[char] == pattern_index:
                pattern_index += 1
                if pattern_index == len(pattern):
                    break
    return pattern_index == len(pattern)

Time and Space Complexity#

  • Time Complexity: We first iterate through the pattern to create the hash map ($O(m)$, where $m$ is the length of pattern). Then we iterate through the s string ($O(n)$). So, the overall time complexity is $O(m + n)$.
  • Space Complexity: In the worst case, if all characters in the pattern are unique, the hash map will store $m$ key - value pairs. So, the space complexity is $O(m)$.

4. Best Practices#

Input Validation#

Always check if the input strings (pattern and s) are non - empty. This can prevent runtime errors like IndexError when trying to access elements of an empty string.

Code Readability#

  • Use meaningful variable names. For example, in the hash map approach, pattern_map clearly indicates that it is a map related to the pattern.
  • Add comments to explain complex logic. For instance, in the hash map approach, a comment can be added to explain how the pattern_index variable is used to track the order.

5. Example Usage#

pattern = "abc"
s1 = "aabbcc"
s2 = "abccba"
print(follows_pattern_brute(pattern, s1))  # True
print(follows_pattern_brute(pattern, s2))  # True
print(follows_pattern_hash(pattern, s1))  # True
print(follows_pattern_hash(pattern, s2))  # True

6. References#

  • Python Documentation
  • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

This blog post has covered different approaches to check if a string follows a given pattern. The hash map approach is generally more efficient when dealing with larger patterns and strings, but the brute - force approach can be simpler for very small input sizes. Understanding the trade - offs between different methods and following best practices will help in writing clean and efficient code for such problems.

2026-07