dist.py

def levenshtein_with_wildcards(str1, str2, wildcard='?', verbose=False):
    """
    Calculate the Levenshtein distance between two strings with support for wildcards.
    
    Args:
        str1 (str): The first string.
        str2 (str): The second string.
        wildcard (str, optional): The wildcard character. Defaults to '?'.
        verbose (bool, optional): If True, prints the DP matrix and explains the process.
        
    Returns:
        int: The Levenshtein distance between the two strings.
        list: If verbose=True, also returns a list of operations performed.
    """
    m, n = len(str1), len(str2)
    
    # Create a matrix of size (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize the first row and column
    for i in range(m + 1):
        dp[i][0] = i
    
    for j in range(n + 1):
        dp[0][j] = j
    
    # Fill the dp matrix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If either character is a wildcard, treat it as a match (cost = 0)
            if str1[i - 1] == wildcard or str2[j - 1] == wildcard:
                dp[i][j] = dp[i - 1][j - 1]  # No cost for wildcard matches
            else:
                cost = 0 if str1[i - 1] == str2[j - 1] else 1
                dp[i][j] = min(
                    dp[i - 1][j] + 1,      # deletion
                    dp[i][j - 1] + 1,      # insertion
                    dp[i - 1][j - 1] + cost  # substitution
                )
    
    if verbose:
        operations = explain_match(str1, str2, dp, wildcard)
        return dp[m][n], operations
    
    return dp[m][n]

def explain_match(str1, str2, dp, wildcard='?'):
    """
    Traces the optimal alignment path and explains each step of the matching process.
    
    Args:
        str1 (str): The first string.
        str2 (str): The second string.
        dp (list): The dynamic programming matrix.
        wildcard (str, optional): The wildcard character. Defaults to '?'.
        
    Returns:
        list: A list of explanation strings for each operation performed.
    """
    m, n = len(str1), len(str2)
    operations = []
    
    # Find the optimal path
    i, j = m, n
    path = []
    
    while i > 0 or j > 0:
        path.append((i, j))
        
        if i == 0:
            j -= 1
        elif j == 0:
            i -= 1
        else:
            substitution_cost = dp[i-1][j-1]
            deletion_cost = dp[i-1][j]
            insertion_cost = dp[i][j-1]
            
            min_cost = min(substitution_cost, deletion_cost, insertion_cost)
            
            if min_cost == substitution_cost:
                i -= 1
                j -= 1
            elif min_cost == deletion_cost:
                i -= 1
            else:
                j -= 1
    
    path.append((0, 0))
    path.reverse()
    
    # Generate explanations for each step
    for idx in range(1, len(path)):
        prev_i, prev_j = path[idx-1]
        curr_i, curr_j = path[idx]
        
        # Diagonal move (match or substitution)
        if curr_i > prev_i and curr_j > prev_j:
            char1 = str1[curr_i-1]
            char2 = str2[curr_j-1]
            
            if char1 == wildcard or char2 == wildcard:
                wildcard_char = char1 if char1 == wildcard else char2
                match_char = char2 if char1 == wildcard else char1
                operations.append(f"Wildcard match: '{wildcard_char}' matches any character, here '{match_char}'")
            elif char1 == char2:
                operations.append(f"Match: '{char1}' matches '{char2}'")
            else:
                operations.append(f"Substitution: Replace '{char1}' with '{char2}'")
        
        # Horizontal move (insertion)
        elif curr_i == prev_i and curr_j > prev_j:
            operations.append(f"Insertion: Insert '{str2[curr_j-1]}'")
        
        # Vertical move (deletion)
        elif curr_i > prev_i and curr_j == prev_j:
            operations.append(f"Deletion: Delete '{str1[curr_i-1]}'")
    
    return operations

def print_match_summary(str1, str2, wildcard='?'):
    """
    Prints a summary of the match between two strings, highlighting wildcards.
    
    Args:
        str1 (str): The first string.
        str2 (str): The second string.
        wildcard (str, optional): The wildcard character. Defaults to '?'.
    """
    distance, operations = levenshtein_with_wildcards(str1, str2, wildcard, verbose=True)
    
    print(f"Comparing '{str1}' and '{str2}' (wildcard: '{wildcard}')")
    print(f"Edit distance: {distance}")
    print("\nMatch process:")
    
    for i, op in enumerate(operations):
        print(f"Step {i+1}: {op}")
    
    # Visual representation
    alignment = []
    i, j = 0, 0
    aligned_str1 = ""
    aligned_str2 = ""
    match_indicators = ""
    
    for op in operations:
        if "match" in op or "Match" in op or "Substitution" in op:
            aligned_str1 += str1[i]
            aligned_str2 += str2[j]
            
            if "Wildcard" in op:
                match_indicators += "*"  # Wildcard match
            elif "Match" in op:
                match_indicators += "|"  # Exact match
            else:
                match_indicators += "X"  # Substitution
            
            i += 1
            j += 1
        elif "Insertion" in op:
            aligned_str1 += "-"
            aligned_str2 += str2[j]
            match_indicators += " "
            j += 1
        elif "Deletion" in op:
            aligned_str1 += str1[i]
            aligned_str2 += "-"
            match_indicators += " "
            i += 1
    
    print("\nAlignment:")
    print(aligned_str1)
    print(match_indicators)
    print(aligned_str2)
    print("\nLegend:")
    print("| = exact match, * = wildcard match, X = substitution, - = gap (insertion/deletion)")
    
    # Summary of wildcard matches
    wildcard_matches = [op for op in operations if "Wildcard" in op]
    if wildcard_matches:
        print("\nWildcard matches:")
        for match in wildcard_matches:
            print(f"- {match}")
    
    return distance, operations

# Example usage
if __name__ == "__main__":
    # Basic examples
    print_match_summary("hello", "hello")       # 0 (identical strings)
    print_match_summary("hello", "hallo")       # 1 (one substitution)
    print_match_summary("he?lo", "hello")       # 0 (wildcard matches 'l')
    print_match_summary("he?lo", "hallo")       # 0 (wildcard matches 'a')
    print_match_summary("h?llo", "hello")       # 0 (wildcard matches 'e')
    print_match_summary("h?llo", "hillo")       # 0 (wildcard matches 'i')
    print_match_summary("c?t", "cat")           # 0 (wildcard matches 'a')
    print_match_summary("c?t", "cut")           # 0 (wildcard matches 'u')
    print_match_summary("w?rd", "word")         # 0 (wildcard matches 'o')
    print_match_summary("d?g", "dog")           # 0 (wildcard matches 'o')