Dadas dos strings de longitud n y n+1. La segunda string contiene todo el carácter de la primera string, pero hay un carácter adicional. Su tarea para encontrar el carácter adicional en la segunda string.
Ejemplos:
Input : string strA = "abcd";
string strB = "cbdae";
Output : e
string B contain all the element
there is a one extra character which is e
Input : string strA = "kxml";
string strB = "klxml";
Output : l
string B contain all the element
there is a one extra character which is l
Método 1 (Fuerza bruta): –
Verifique con dos para bucle.
Complejidad de tiempo:- O(n^2)
Complejidad de espacio:- O(1).
Método 2 (mapa hash): –
Cree una tabla hash vacía e inserte todos los caracteres de la segunda string. Ahora elimine todos los caracteres de la primera string. El carácter restante es el carácter adicional.
Complejidad de Tiempo:- O(n)
Espacio Auxiliar:- O(n).
C++
// CPP program to find extra character in one
// string
#include <bits/stdc++.h>
using namespace std;
char findExtraCharcter(string strA, string strB)
{
// store string values in map
unordered_map<char, int> m1;
// store second string in map with frequency
for (int i = 0; i < strB.length(); i++)
m1[strB[i]]++;
// store first string in map with frequency
for (int i = 0; i < strA.length(); i++)
m1[strA[i]]--;
for (auto h1 = m1.begin(); h1 != m1.end(); h1++) {
// if the frequency is 1 then this
// character is which is added extra
if (h1->second == 1)
return h1->first;
}
}
int main()
{
// given string
string strA = "abcd";
string strB = "cbdad";
// find Extra Character
cout << findExtraCharcter(strA, strB);
}
Java
// Java program to find extra character in one
// string
class GFG
{
static char findExtraCharcter(char []strA, char[] strB)
{
// store string values in map
int[] m1 = new int[256];
// store second string in map with frequency
for (int i = 0; i < strB.length; i++)
m1[strB[i]]++;
// store first string in map with frequency
for (int i = 0; i < strA.length; i++)
m1[strA[i]]--;
for (int i=0;i<m1.length;i++)
{
// if the frequency is 1 then this
// character is which is added extra
if (m1[i]== 1)
return (char) i;
}
return Character.MIN_VALUE;
}
// Driver code
public static void main(String[] args)
{
// given string
String strA = "abcd";
String strB = "cbdad";
// find Extra Character
System.out.println(findExtraCharcter(strA.toCharArray(), strB.toCharArray()));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find extra character
# in one string
def findExtraCharacter(strA, strB):
# store string values in map
m1 = {}
# store second string in map
# with frequency
for i in strB:
if i in m1:
m1[i] += 1
else:
m1[i] = 1
# store first string in map
# with frequency
for i in strA:
m1[i] -= 1
for h1 in m1:
# if the frequency is 1 then this
# character is which is added extra
if m1[h1] == 1:
return h1
# Driver Code
if __name__ == "__main__":
# given string
strA = 'abcd'
strB = 'cbdad'
# find Extra Character
print(findExtraCharacter(strA, strB))
# This code is contributed by
# sanjeev2552
C#
// C# program to find extra character in one
// string
using System;
class GFG
{
static char findExtraCharcter(char []strA, char[] strB)
{
// store string values in map
int[] m1 = new int[256];
// store second string in map with frequency
for (int i = 0; i < strB.Length; i++)
m1[strB[i]]++;
// store first string in map with frequency
for (int i = 0; i < strA.Length; i++)
m1[strA[i]]--;
for (int i = 0; i < m1.Length; i++)
{
// if the frequency is 1 then this
// character is which is added extra
if (m1[i]== 1)
return (char) i;
}
return char.MinValue;
}
// Driver code
public static void Main(String[] args)
{
// given string
String strA = "abcd";
String strB = "cbdad";
// find Extra Character
Console.WriteLine(findExtraCharcter(strA.ToCharArray(),
strB.ToCharArray()));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find extra character in one
// string
function findExtraCharcter(strA,strB)
{
// store string values in map
let m1 = new Array(256);
for(let i = 0; i < 256; i++)
m1[i] = 0;
// store second string in map with frequency
for (let i = 0; i < strB.length; i++)
m1[strB[i].charCodeAt(0)]++;
// store first string in map with frequency
for (let i = 0; i < strA.length; i++)
m1[strA[i].charCodeAt(0)]--;
for (let i = 0; i < m1.length; i++)
{
// if the frequency is 1 then this
// character is which is added extra
if (m1[i] == 1)
return String.fromCharCode(i);
}
return Number.MIN_VALUE;
}
// given string
let strA = "abcd";
let strB = "cbdad";
// find Extra Character
document.write(findExtraCharcter(strA.split(""), strB.split("")));
// This code is contributed by rag2127
</script>
Producción:
d
Método 3 (Bits): –
atraviesa la primera y la segunda string desde el comienzo con la operación xor al final, obtienes el carácter que es extra.
Complejidad de tiempo:- O(n+n+1)
Complejidad de espacio:- O(1).
C++
// CPP program to find extra character in one
// string
#include <iostream>
using namespace std;
char findExtraCharcter(string strA, string strB)
{
// result store the result
int res = 0, i;
// traverse string A till end and
// xor with res
for (i = 0; i < strA.length(); i++) {
// xor with res
res ^= strA[i];
}
// traverse string B till end and
// xor with res
for (i = 0; i < strB.length(); i++) {
// xor with res
res ^= strB[i];
}
// print result at the end
return ((char)(res));
}
int main()
{
// given string
string strA = "abcd";
string strB = "cbdad";
cout << findExtraCharcter(strA, strB);
return 0;
}
Java
// Java program to find extra
// character in one string
import java.io.*;
class GFG {
static char findExtraCharcter(String strA,
String strB)
{
// result store the result
int res = 0, i;
// traverse string A till
// end and xor with res
for (i = 0; i < strA.length(); i++)
{
// xor with res
res ^= strA.charAt(i);
}
// traverse string B till end and
// xor with res
for (i = 0; i < strB.length(); i++)
{
// xor with res
res ^= strB.charAt(i);
}
// print result at the end
return ((char)(res));
}
// Driver code
public static void main(String args[])
{
// given string
String strA = "abcd";
String strB = "cbdad";
System.out.println(findExtraCharcter(strA, strB));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python 3
# Python 3 program to find # extra character in one string def findExtraCharcter(strA, strB) : # result store the result res = 0 # traverse string A till # end and xor with res for i in range(0,len(strA)) : # xor with res res =res ^ (ord)(strA[i]) # traverse string B till # end and xor with res for i in range(0,len(strB)) : # xor with res res = res ^ (ord)(strB[i]) # print result at the end return ((chr)(res)); # given string strA = "abcd" strB = "cbdad" print(findExtraCharcter(strA, strB)) # This code is contributed by Nikita Tiwari.
C#
// C# program to find extra character
// in one string
using System;
class GFG {
static char findExtraCharcter(string strA,
string strB)
{
// result store the result
int res = 0, i;
// traverse string A till end and
// xor with res
for (i = 0; i < strA.Length; i++) {
// xor with res
res ^= strA[i];
}
// traverse string B till end and
// xor with res
for (i = 0; i < strB.Length; i++) {
// xor with res
res ^= strB[i];
}
// print result at the end
return ((char)(res));
}
// Driver Code
public static void Main()
{
// given string
string strA = "abcd";
string strB = "cbdad";
Console.WriteLine(
findExtraCharcter(strA, strB));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to find extra character in
// one string
function findExtraCharcter($strA, $strB)
{
// result store the result
$res = 0;
// traverse string A till end and
// xor with res
for ($i = 0; $i < strlen($strA); $i++)
{
// xor with res
$res ^= ord($strA[$i]);
}
// traverse string B till end and
// xor with res
for ($i = 0; $i < strlen($strB); $i++)
{
// xor with res
$res ^= ord($strB[$i]);
}
// print result at the end
return $res;
}
// Driver code
$strA = "abcd";
$strB = "cbdad";
echo chr(findExtraCharcter($strA, $strB));
// This code is contributed by Manish Shaw
// (manishshaw1)
?>
Javascript
<script>
// Javascript program to find extra character in
// one string
function findExtraCharcter(strA, strB)
{
// result store the result
let res = 0;
// traverse string A till end and
// xor with res
for (let i = 0; i < strA.length; i++)
{
// xor with res
res ^= strA.charCodeAt(i);
}
// traverse string B till end and
// xor with res
for (let i = 0; i < strB.length; i++)
{
// xor with res
res ^= strB.charCodeAt(i);
}
// print result at the end
return res;
}
// Driver code
let strA = "abcd";
let strB = "cbdad";
document.write(String.fromCharCode(findExtraCharcter(strA, strB)));
// This code is contributed by gfgking
</script>
Producción:
d
Método 4 (Código de caracteres): –
Agregue los códigos de caracteres de ambas strings. Menos los códigos de caracteres de una string más pequeña de una string más grande y convierte el entero resultante en un carácter.
Complejidad de Tiempo:- O(n)
Espacio Auxiliar:- O(1).
C++
// C++ program to find extra
// character in one string
#include<bits/stdc++.h>
using namespace std;
char findExtraCharacter(string s1, string s2)
{
string smallStr;
string largeStr;
// Determine string with extra character.
if(s1.size() > s2.size())
{
smallStr = s2;
largeStr = s1;
}
else
{
smallStr = s1;
largeStr = s2;
}
int smallStrCodeTotal = 0;
int largeStrCodeTotal = 0;
int i = 0;
// Add character codes of both the strings
for(; i < smallStr.size(); i++)
{
smallStrCodeTotal += smallStr[i];
largeStrCodeTotal += largeStr[i];
}
// Add last character code of large string.
largeStrCodeTotal += largeStr[i];
// Minus the character code of smaller string from
// the character code of large string.
// The result will be the extra character code.
int intChar = largeStrCodeTotal - smallStrCodeTotal;
return (char)intChar;
}
// Driver code
int main()
{
string s1 = "abcd";
string s2 = "cbdae";
char extraChar = findExtraCharacter(s1, s2);
cout<<"Extra character: " <<(extraChar)<<endl;
return 0;
}
// This code is contributed by Princi Singh
Java
// Java program to find extra
// character in one string
public class Test {
private static char findExtraCharacter(String s1, String s2) {
String smallStr;
String largeStr;
// Determine String with extra character.
if(s1.length() > s2.length()) {
smallStr = s2;
largeStr = s1;
} else {
smallStr = s1;
largeStr = s2;
}
int smallStrCodeTotal = 0;
int largeStrCodeTotal = 0;
int i = 0;
// Add character codes of both the strings
for(; i < smallStr.length(); i++) {
smallStrCodeTotal += smallStr.charAt(i);
largeStrCodeTotal += largeStr.charAt(i);
}
// Add last character code of large String.
largeStrCodeTotal += largeStr.charAt(i);
// Minus the character code of smaller string from
// the character code of large string.
// The result will be the extra character code.
int intChar = largeStrCodeTotal - smallStrCodeTotal;
return (char)intChar;
}
public static void main(String[] args) {
String s1 = "abcd";
String s2 = "cbdae";
char extraChar = findExtraCharacter(s1, s2);
System.out.println("Extra character: " + extraChar);
}
}
/*This code is contributed by Amol Bhosale.*/
Python3
# Python Program to find extra character in one string
def findExtraCharacter(s1,s2):
smallStr = ""
largeStr = ""
# Determine string with extra character
if(len(s1) > len(s2)):
smallStr = s2
largeStr = s1
else:
smallStr = s1
largeStr = s2
smallStrCodeTotal = 0
largeStrCodeTotal = 0
i = 0
# Add Character codes of both the strings
while(i < len(smallStr)):
smallStrCodeTotal += ord(smallStr[i])
largeStrCodeTotal += ord(largeStr[i])
i += 1
# Add last character code of large string
largeStrCodeTotal += ord(largeStr[i])
# Minus the character code of smaller string
# from the character code of large string
# The result will be the extra character code
intChar = largeStrCodeTotal - smallStrCodeTotal
return chr(intChar)
# Driver code
s1 = "abcd"
s2 = "cbdae"
extraChar = findExtraCharacter(s1, s2)
print("Extra Character:", extraChar)
# This code is contributed by simranjenny84
C#
// C# program to find extra
// character in one string
using System;
class GFG
{
private static char findExtraCharacter(String s1,
String s2)
{
String smallStr;
String largeStr;
// Determine String with extra character.
if(s1.Length > s2.Length)
{
smallStr = s2;
largeStr = s1;
}
else
{
smallStr = s1;
largeStr = s2;
}
int smallStrCodeTotal = 0;
int largeStrCodeTotal = 0;
int i = 0;
// Add character codes of both the strings
for(; i < smallStr.Length; i++)
{
smallStrCodeTotal += smallStr[i];
largeStrCodeTotal += largeStr[i];
}
// Add last character code of large String.
largeStrCodeTotal += largeStr[i];
// Minus the character code of smaller string
// from the character code of large string.
// The result will be the extra character code.
int intChar = largeStrCodeTotal -
smallStrCodeTotal;
return (char)intChar;
}
public static void Main(String[] args)
{
String s1 = "abcd";
String s2 = "cbdae";
char extraChar = findExtraCharacter(s1, s2);
Console.WriteLine("Extra character: " +
extraChar);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find extra
// character in one string
function findExtraCharacter(s1, s2)
{
let smallStr;
let largeStr;
// Determine String with extra character.
if(s1.length > s2.length)
{
smallStr = s2;
largeStr = s1;
}
else
{
smallStr = s1;
largeStr = s2;
}
let smallStrCodeTotal = 0;
let largeStrCodeTotal = 0;
let i = 0;
// Add character codes of both the strings
for(; i < smallStr.length; i++)
{
smallStrCodeTotal += smallStr[i].charCodeAt(0);
largeStrCodeTotal += largeStr[i].charCodeAt(0);
}
// Add last character code of large String.
largeStrCodeTotal += largeStr[i].charCodeAt(0);
// Minus the character code of smaller string from
// the character code of large string.
// The result will be the extra character code.
let intChar = largeStrCodeTotal - smallStrCodeTotal;
return String.fromCharCode(intChar);
}
let s1 = "abcd";
let s2 = "cbdae";
let extraChar = findExtraCharacter(s1, s2);
document.write("Extra character: " + extraChar);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Extra character: e
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA