Educative《从零基础学习Python 3》首考：如何实现符合要求的detect_pattern字符串模式检测函数？

This problem comes from the first exam of Learn Python 3 from Scratch on Educative.io, titled Detecting String Pattern. We need to write a function detect_pattern that returns True if two strings share the same character pattern, following these rules:

1. The two strings must be the same length (after removing spaces, per examples like - - - vs aaa).
2. For any two positions in the first string, the characters are equal if and only if the characters in the corresponding positions of the second string are also equal.

Example Cases #

Constraints #

• The function takes two strings as parameters.
• We cannot use lists, sets, dictionaries, or other extra data structures—only new strings are allowed.
• The function must return the same result regardless of the order of the input parameters.

Your current code only checks if the lengths (after removing spaces) are equal, which fails most test cases. Here's how to fix it:

Solution Approach #

The key idea is to generate a pattern signature for each cleaned string (with spaces removed). This signature replaces each unique character with a sequential number (as a string) based on the order it first appears. For example:

• "aba" becomes "010"
• "xyz" becomes "012"
• "---" becomes "000"
• "toetoe" becomes "010101"

If both strings have identical signatures, they share the same pattern. We can generate these signatures using only string operations, which fits the constraints.

Updated Code #

import unittest

def generate_pattern_signature(s):
    # Generate a pattern signature using only string operations
    signature = ""
    seen_chars = ""
    for char in s:
        if char in seen_chars:
            # Find the index of the first occurrence of char in seen_chars
            idx = seen_chars.index(char)
            signature += str(idx)
        else:
            # Use the length of seen_chars as the new index
            signature += str(len(seen_chars))
            seen_chars += char
    return signature

def detect_pattern(s1, s2):
    # Remove all spaces from both strings first
    s1_clean = s1.replace(" ", "")
    s2_clean = s2.replace(" ", "")
    
    # First check: lengths must match
    if len(s1_clean) != len(s2_clean):
        return False
    
    # Generate signatures and compare
    sig1 = generate_pattern_signature(s1_clean)
    sig2 = generate_pattern_signature(s2_clean)
    
    return sig1 == sig2

class TestDetectPattern(unittest.TestCase):
    def test_basics(self):
        self.assertEqual(detect_pattern("", ""), True)
        self.assertEqual(detect_pattern("a", "a"), True)
        self.assertEqual(detect_pattern("x", "y"), True)
        self.assertEqual(detect_pattern("ab", "xy"), True)
        self.assertEqual(detect_pattern("aba", "xyz"), False)
        self.assertEqual(detect_pattern("- - -", "xyz"), False)
        self.assertEqual(detect_pattern("- - -", "aaa"), True)
        self.assertEqual(detect_pattern("xyzxyz", "toetoe"), True)
        self.assertEqual(detect_pattern("xyzxyz", "toetoa"), False)
        self.assertEqual(detect_pattern("aaabbbcccd", "eeefffgggz"), True)
        self.assertEqual(detect_pattern("cbacbacba", "xyzxyzxyz"), True)
        self.assertEqual(detect_pattern("abcdefghijk", "lmnopqrstuv"), True)
        self.assertEqual(detect_pattern("asasasasas", "xxxxxyyyyy"), False)
        self.assertEqual(detect_pattern("ascneencsa", "aeiouaeiou"), False)
        self.assertEqual(detect_pattern("aaasssiiii", "gggdddfffh"), False)

if __name__ == '__main__':
    unittest.main()

Explanation #

1. Cleaning the Input: We first remove all spaces from both strings to handle cases like - - - (which becomes ---).
2. Generating Signatures:
   • seen_chars keeps track of characters we've already encountered in the string.
   • For each character, if it's in seen_chars, we append the index of its first occurrence to the signature.
   • If it's new, we append the current length of seen_chars (which acts as a unique sequential ID) and add the character to seen_chars.
3. Comparing Signatures: If the signatures match, the strings have the same pattern—this satisfies the "if and only if" rule from the problem statement.
4. Order Independence: Since we're comparing signatures regardless of input order, swapping s1 and s2 will return the same result.

This implementation passes all test cases while adhering strictly to the constraints.

内容的提问来源于stack exchange，提问作者Deadjim