Dada una array de strings str[] de longitud N , que consta de strings de la misma longitud, la tarea es encontrar la string que solo difiere en un solo carácter de todas las strings dadas. Si no se puede generar tal string, imprima -1 . En caso de múltiples respuestas posibles, imprima cualquiera de ellas.
Ejemplo:
Entrada: str[] = { “abac”, “zdac”, “bdac”}
Salida: adac
Explicación:
La string “adac” difiere de todas las strings dadas por un solo carácter.Entrada: str[] = { “geeks”, “teeds”}
Salida: teeks
Enfoque: siga los pasos a continuación para resolver el problema:
- Establezca la primera string como la respuesta.
- Ahora, reemplace el primer carácter de la string por todos los caracteres posibles y verifique si difiere en un solo carácter de las otras strings o no.
- Repita este proceso para todos los caracteres de la primera string.
- Si se encuentra alguna string del tipo requerido en el paso anterior, imprima la string.
- Si no surge tal situación en la que reemplazar un solo carácter de la primera string genera una string del tipo requerido, imprima -1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to check if a given string
// differs by a single character from
// all the strings in an array
bool check(string ans, vector<string>& s,
int n, int m)
{
// Traverse over the strings
for (int i = 1; i < n; ++i) {
// Stores the count of characters
// differing from the strings
int count = 0;
for (int j = 0; j < m; ++j) {
if (ans[j] != s[i][j])
count++;
}
// If differs by more than one
// character
if (count > 1)
return false;
}
return true;
}
// Function to find the string which only
// differ at one position from the all
// given strings of the array
string findString(vector<string>& s)
{
// Size of the array
int n = s.size();
// Length of a string
int m = s[0].size();
string ans = s[0];
int flag = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 26; ++j) {
string x = ans;
// Replace i-th character by all
// possible characters
x[i] = (j + 'a');
// Check if it differs by a
// single character from all
// other strings
if (check(x, s, n, m)) {
ans = x;
flag = 1;
break;
}
}
// If desired string is obtained
if (flag == 1)
break;
}
// Print the answer
if (flag == 0)
return "-1";
else
return ans;
}
// Driver code
int main()
{
vector<string> s = { "geeks", "teeds" };
// Function call
cout << findString(s) << endl;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check if a given string
// differs by a single character from
// all the strings in an array
static boolean check(String ans, String[] s,
int n, int m)
{
// Traverse over the strings
for(int i = 1; i < n; ++i)
{
// Stores the count of characters
// differing from the strings
int count = 0;
for(int j = 0; j < m; ++j)
{
if (ans.charAt(j) != s[i].charAt(j))
count++;
}
// If differs by more than one
// character
if (count > 1)
return false;
}
return true;
}
// Function to find the string which only
// differ at one position from the all
// given strings of the array
static String findString(String[] s)
{
// Size of the array
int n = s.length;
String ans = s[0];
// Length of a string
int m = ans.length();
int flag = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < 26; ++j)
{
String x = ans;
// Replace i-th character by all
// possible characters
x = x.replace(x.charAt(i), (char)(j + 'a'));
// Check if it differs by a
// single character from all
// other strings
if (check(x, s, n, m))
{
ans = x;
flag = 1;
break;
}
}
// If desired string is obtained
if (flag == 1)
break;
}
// Print the answer
if (flag == 0)
return "-1";
else
return ans;
}
// Driver code
public static void main(String []args)
{
String s[] = { "geeks", "teeds" };
// Function call
System.out.println(findString(s));
}
}
// This code is contributed by chitranayal
Python3
# Python3 program to implement
# the above approach
# Function to check if a given string
# differs by a single character from
# all the strings in an array
def check(ans, s, n, m):
# Traverse over the strings
for i in range(1, n):
# Stores the count of characters
# differing from the strings
count = 0
for j in range(m):
if(ans[j] != s[i][j]):
count += 1
# If differs by more than one
# character
if(count > 1):
return False
return True
# Function to find the string which only
# differ at one position from the all
# given strings of the array
def findString(s):
# Size of the array
n = len(s)
# Length of a string
m = len(s[0])
ans = s[0]
flag = 0
for i in range(m):
for j in range(26):
x = list(ans)
# Replace i-th character by all
# possible characters
x[i] = chr(j + ord('a'))
# Check if it differs by a
# single character from all
# other strings
if(check(x, s, n, m)):
ans = x
flag = 1
break
# If desired string is obtained
if(flag == 1):
break
# Print the answer
if(flag == 0):
return "-1"
else:
return ''.join(ans)
# Driver Code
# Given array of strings
s = [ "geeks", "teeds" ]
# Function call
print(findString(s))
# This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check if a given string
// differs by a single character from
// all the strings in an array
static bool check(String ans, String[] s,
int n, int m)
{
// Traverse over the strings
for(int i = 1; i < n; ++i)
{
// Stores the count of characters
// differing from the strings
int count = 0;
for(int j = 0; j < m; ++j)
{
if (ans[j] != s[i][j])
count++;
}
// If differs by more than one
// character
if (count > 1)
return false;
}
return true;
}
// Function to find the string which only
// differ at one position from the all
// given strings of the array
static String findString(String[] s)
{
// Size of the array
int n = s.Length;
String ans = s[0];
// Length of a string
int m = ans.Length;
int flag = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < 26; ++j)
{
String x = ans;
// Replace i-th character by all
// possible characters
x = x.Replace(x[i], (char)(j + 'a'));
// Check if it differs by a
// single character from all
// other strings
if (check(x, s, n, m))
{
ans = x;
flag = 1;
break;
}
}
// If desired string is obtained
if (flag == 1)
break;
}
// Print the answer
if (flag == 0)
return "-1";
else
return ans;
}
// Driver code
public static void Main(String []args)
{
String []s = { "geeks", "teeds" };
// Function call
Console.WriteLine(findString(s));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if a given string
// differs by a single character from
// all the strings in an array
function check(ans, s, n, m)
{
// Traverse over the strings
for (var i = 1; i < n; ++i)
{
// Stores the count of characters
// differing from the strings
var count = 0;
for (var j = 0; j < m; ++j) {
if (ans[j] !== s[i][j]) count++;
}
// If differs by more than one
// character
if (count > 1) return false;
}
return true;
}
// Function to find the string which only
// differ at one position from the all
// given strings of the array
function findString(s)
{
// Size of the array
var n = s.length;
var ans = s[0];
// Length of a string
var m = ans.length;
var flag = 0;
for (var i = 0; i < m; ++i) {
for (var j = 0; j < 26; ++j) {
var x = ans;
// Replace i-th character by all
// possible characters
x = x.replace(x[i], String.fromCharCode(j + "a".charCodeAt(0)));
// Check if it differs by a
// single character from all
// other strings
if (check(x, s, n, m)) {
ans = x;
flag = 1;
break;
}
}
// If desired string is obtained
if (flag === 1) break;
}
// Print the answer
if (flag === 0) return "-1";
else return ans;
}
// Driver code
var s = ["geeks", "teeds"];
// Function call
document.write(findString(s));
// This code is contributed by rdtank.
</script>
Producción:
teeks
Complejidad de Tiempo: O(N * M 2 * 26)
Espacio Auxiliar: O(M)