Recuento de pares de strings que difieren exactamente en una posición

Dada una array arr[] de strings de igual longitud. La tarea es calcular el número total de pares de cuerdas que difieren exactamente en una posición. Ejemplos:

Entrada: arr[] = {“abc”, “abd”, “bbd”} Salida: 2 (abc, abd) y (abd, bbd) son los únicos pares válidos. Entrada: arr[] = {“def”, “deg”, “dmf”, “xef”, “dxg”} Salida: 4

Método 1: para cada par posible, verifique si ambas strings difieren exactamente en una sola posición de índice con un solo recorrido de las strings. Método 2: se pueden comparar dos strings de la siguiente manera para verificar si difieren en una sola posición de índice:

Sea str1 = “abc” y str2 = “adc” Para str1 , agregue “#bc” , “a#c” y “ab#” a un conjunto . Ahora, para str2 , genere la string de manera similar y si alguna de las strings generadas ya está presente en el conjunto, ambas strings difieren exactamente en 1 posición de índice. Por ejemplo, “a#c” es una de las strings generadas. Tenga en cuenta que se usa «#» porque no formará parte de ninguna de las strings originales.

A continuación se muestra la implementación del enfoque anterior: 

// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of same pairs
int pairCount(map<string, int> &d)
{
    int sum = 0;
    for (auto i : d)
        sum += (i.second * (i.second - 1)) / 2;
 
    return sum;
}
 
// Function to return total number of strings
// which satisfy required condition
int difference(vector<string> &array, int m)
{
    // Dictionary changed will store strings
    // with wild cards
    // Dictionary same will store strings
    // that are equal
    map<string, int> changed, same;
 
    // Iterating for all strings in the given array
    for (auto s : array)
    {
        // If we found the string then increment by 1
        // Else it will get default value 0
        same[s]++;
 
        // Iterating on a single string
        for (int i = 0; i < m; i++)
        {
            // Adding special symbol to the string
            string t = s.substr(0, i) + "//" + s.substr(i + 1);
 
            // Incrementing the string if found
            // Else it will get default value 0
            changed[t]++;
        }
    }
 
    // Return counted pairs - equal pairs
    return pairCount(changed) - pairCount(same) * m;
}
 
// Driver Code
int main()
{
    int n = 3, m = 3;
    vector<string> array = {"abc", "abd", "bbd"};
    cout << difference(array, m) << endl;
 
    return 0;
}
 
// This code is contributed by
// sanjeev2552

# Python3 implementation of the approach
 
# Function to return the count of same pairs
def pair_count(d):
    return sum((i*(i-1))//2 for i in d.values())
 
 
# Function to return total number of strings
# which satisfy required condition
def Difference(array, m):
     
    # Dictionary changed will store strings
    # with wild cards
    # Dictionary same will store strings
    # that are equal
    changed, same = {}, {}
     
    # Iterating for all strings in the given array
    for s in array:
         
        # If we found the string then increment by 1
        # Else it will get default value 0
        same[s]= same.get(s, 0)+1
         
        # Iterating on a single string
        for i in range(m):
            # Adding special symbol to the string
            t = s[:i]+'#'+s[i + 1:]
             
            # Incrementing the string if found
            # Else it will get default value 0
            changed[t]= changed.get(t, 0)+1
 
    # Return counted pairs - equal pairs
    return pair_count(changed) - pair_count(same)*m
 
# Driver code
if __name__=="__main__":
    n, m = 3, 3
    array =["abc", "abd", "bbd"]
    print(Difference(array, m))

<script>
 
// JavaScript implementation of the approach
 
// Function to return the count of same pairs
function pairCount(d)
{
    let sum = 0;
    for (let [i,j] of d)
        sum += Math.floor((j * (j - 1)) / 2);
 
    return sum;
}
 
// Function to return total number of strings
// which satisfy required condition
function difference(array,m)
{
    // Dictionary changed will store strings
    // with wild cards
    // Dictionary same will store strings
    // that are equal
    let changed = new Map(), same = new Map();
 
    // Iterating for all strings in the given array
    for (let s of array)
    {
        // If we found the string then increment by 1
        // Else it will get default value 0
        if(same.has(s)){
            same.set(s,same.get(s)+1);
        }
        else same.set(s,1);
 
        // Iterating on a single string
        for (let i = 0; i < m; i++)
        {
            // Adding special symbol to the string
            let t = s.substring(0, i) + "//" + s.substring(i + 1,);
 
            // Incrementing the string if found
            // Else it will get default value 0
            if(changed.has(t)){
                changed.set(t,changed.get(t)+1);
            }
            else changed.set(t,1);
        }
    }
 
    // Return counted pairs - equal pairs
    return pairCount(changed) - pairCount(same) * m;
}
 
// Driver Code
 
let n = 3, m = 3;
let array = ["abc", "abd", "bbd"];
document.write(difference(array, m),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad del tiempo: O(n*m)

Complejidad espacial : O(n+m)