Dadas dos strings S1 y S2 de igual longitud, la tarea es determinar si S2 es una forma codificada de S1.
String codificada:
dada la string str , podemos representarla como un árbol binario dividiéndola en dos substrings no vacías de forma recursiva.
Nota: la string codificada no es lo mismo que un anagrama
. A continuación se muestra una posible representación de str = «codificador» :
coder
/ \
co der
/ \ / \
c o d er
/ \
e r
Para codificar la string, podemos elegir cualquier Node que no sea hoja e intercambiar sus dos hijos.
Supongamos que elegimos el Node «co» e intercambiamos sus dos hijos, produce una string codificada «ocder».
ocder
/ \
oc der
/ \ / \
o c d er
/ \
e r
Por lo tanto, «ocder» es una string codificada de «codificador» .
De manera similar, si continuamos intercambiando los elementos secundarios de los Nodes «der» y «er» , se produce una string codificada «ocred» .
ocred
/ \
oc red
/ \ / \
o c re d
/ \
r e
Por lo tanto, «ocred» es una string codificada de «codificador» .
Ejemplos:
Entrada: S1=”coder”, S2=”ocder”
Salida: Sí
Explicación:
“ocder” es una forma codificada de “coder”
Entrada: S1=”abcde”, S2=”caebd”
Salida: No
Explicación:
“caebd” no es una forma codificada de «abcde»
Enfoque
Para resolver este problema, estamos utilizando el enfoque Divide and Conquer .
Dadas dos strings de igual longitud (digamos n+1), S1[0…n] y S2[0…n]. Si S2 es una forma codificada de S1, entonces debe existir un índice i tal que al menos una de las siguientes condiciones sea verdadera:
- S2[0…i] es una string codificada de S1[0…i] y S2[i+1…n] es una string codificada de S1[i+1…n].
- S2[0…i] es una string codificada de S1[ni…n] y S2[i+1…n] es una string codificada de S1[0…ni-1].
Nota: un paso de optimización a considerar aquí es verificar de antemano si las dos strings son anagramas entre sí. Si no, indica que las strings contienen caracteres diferentes y no pueden ser una forma codificada de la otra.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to check if a
// given string is a scrambled
// form of another string
#include <bits/stdc++.h>
using namespace std;
bool isScramble(string S1, string S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.length() != S2.length()) {
return false;
}
int n = S1.length();
// Empty strings are scramble strings
if (n == 0) {
return true;
}
// Equal strings are scramble strings
if (S1 == S2) {
return true;
}
// Check for the condition of anagram
string copy_S1 = S1, copy_S2 = S2;
sort(copy_S1.begin(), copy_S1.end());
sort(copy_S2.begin(), copy_S2.end());
if (copy_S1 != copy_S2) {
return false;
}
for (int i = 1; i < n; i++) {
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.substr(0, i), S2.substr(0, i))
&& isScramble(S1.substr(i, n - i),
S2.substr(i, n - i))) {
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.substr(0, i),
S2.substr(n - i, i))
&& isScramble(S1.substr(i, n - i),
S2.substr(0, n - i))) {
return true;
}
}
// If none of the above
// conditions are satisfied
return false;
}
// Driver Code
int main()
{
string S1 = "coder";
string S2 = "ocred";
if (isScramble(S1, S2)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program to check if a
// given string is a scrambled
// form of another string
import java.util.*;
class GFG{
static boolean isScramble(String S1,
String S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.length() != S2.length())
{
return false;
}
int n = S1.length();
// Empty strings are scramble strings
if (n == 0)
{
return true;
}
// Equal strings are scramble strings
if (S1.equals(S2))
{
return true;
}
// Converting string to
// character array
char[] tempArray1 = S1.toCharArray();
char[] tempArray2 = S2.toCharArray();
// Checking condition for Anagram
Arrays.sort(tempArray1);
Arrays.sort(tempArray2);
String copy_S1 = new String(tempArray1);
String copy_S2 = new String(tempArray2);
if (!copy_S1.equals(copy_S2))
{
return false;
}
for(int i = 1; i < n; i++)
{
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.substring(0, i),
S2.substring(0, i)) &&
isScramble(S1.substring(i, n),
S2.substring(i, n)))
{
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.substring(n - i, n),
S2.substring(0, i)) &&
isScramble(S1.substring(0, n - i),
S2.substring(i, n)))
{
return true;
}
}
// If none of the above
// conditions are satisfied
return false;
}
// Driver Code
public static void main(String[] args)
{
String S1 = "coder";
String S2 = "ocred";
if (isScramble(S1, S2))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by dadi madhav
Python3
# Python3 program to check if a
# given string is a scrambled
# form of another string
def isScramble(S1: str, S2: str):
# Strings of non-equal length
# cant' be scramble strings
if len(S1) != len(S2):
return False
n = len(S1)
# Empty strings are scramble strings
if not n:
return True
# Equal strings are scramble strings
if S1 == S2:
return True
# Check for the condition of anagram
if sorted(S1) != sorted(S2):
return False
for i in range(1, n):
# Check if S2[0...i] is a scrambled
# string of S1[0...i] and if S2[i+1...n]
# is a scrambled string of S1[i+1...n]
if (isScramble(S1[:i], S2[:i]) and
isScramble(S1[i:], S2[i:])):
return True
# Check if S2[0...i] is a scrambled
# string of S1[n-i...n] and S2[i+1...n]
# is a scramble string of S1[0...n-i-1]
if (isScramble(S1[-i:], S2[:i]) and
isScramble(S1[:-i], S2[i:])):
return True
# If none of the above
# conditions are satisfied
return False
# Driver Code
if __name__ == "__main__":
S1 = "coder"
S2 = "ocred"
if (isScramble(S1, S2)):
print("Yes")
else:
print("No")
# This code is contributed by sgshah2
C#
// C# program to check if a
// given string is a scrambled
// form of another string
using System;
using System.Collections.Generic;
class GFG {
static bool isScramble(string S1, string S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.Length != S2.Length)
{
return false;
}
int n = S1.Length;
// Empty strings are scramble strings
if (n == 0)
{
return true;
}
// Equal strings are scramble strings
if (S1.Equals(S2))
{
return true;
}
// Converting string to
// character array
char[] tempArray1 = S1.ToCharArray();
char[] tempArray2 = S2.ToCharArray();
// Checking condition for Anagram
Array.Sort(tempArray1);
Array.Sort(tempArray2);
string copy_S1 = new string(tempArray1);
string copy_S2 = new string(tempArray2);
if (!copy_S1.Equals(copy_S2))
{
return false;
}
for(int i = 1; i < n; i++)
{
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.Substring(0, i),
S2.Substring(0, i)) &&
isScramble(S1.Substring(i, n - i),
S2.Substring(i, n - i)))
{
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.Substring(0, i),
S2.Substring(n - i, i)) &&
isScramble(S1.Substring(i, n - i),
S2.Substring(0, n - i)))
{
return true;
}
}
// If none of the above
// conditions are satisfied
return false;
}
// Driver code
static void Main()
{
string S1 = "coder";
string S2 = "ocred";
if (isScramble(S1, S2))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to check if a
// given string is a scrambled
// form of another string
function isScramble(S1, S2)
{
// Strings of non-equal length
// can't be scramble strings
if (S1.length != S2.length)
{
return false;
}
let n = S1.length;
// Empty strings are scramble strings
if (n == 0)
{
return true;
}
// Equal strings are scramble strings
if (S1 == S2)
{
return true;
}
// Converting string to
// character array
let tempArray1 = S1.split('');
let tempArray2 = S2.split('');
// Checking condition for Anagram
tempArray1.sort();
tempArray2.sort();
let copy_S1 = tempArray1.join("");
let copy_S2 = tempArray2.join("");
if (copy_S1 != copy_S2)
{
return false;
}
for(let i = 1; i < n; i++)
{
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.substring(0, i),
S2.substring(0, i)) &&
isScramble(S1.substring(i, i + n),
S2.substring(i, i + n)))
{
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.substring(n - i, n - i + n),
S2.substring(0, i)) &&
isScramble(S1.substring(0, n - i),
S2.substring(i, i + n)))
{
return true;
}
}
// If none of the above
// conditions are satisfied
return false;
}
let S1 = "coder";
let S2 = "ocred";
if (isScramble(S1, S2))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by decode2207.
</script>
Producción
Yes
Complejidad de tiempo : O(2^k + 2^(nk)), donde k y nk son la longitud de las dos substrings.
Espacio auxiliar : O(2^N), pila de recursión.
Solución de programación dinámica: el código recursivo anterior se puede optimizar almacenando valores booleanos de substrings en un mapa desordenado, por lo que si las mismas substrings deben verificarse nuevamente, podemos obtener fácilmente el valor del mapa en lugar de realizar llamadas a funciones.
Código memorizado:
C++
// C++ Program to check if a
// given string is a scrambled
// form of another string
#include <bits/stdc++.h>
using namespace std;
// map declaration for storing key value pair
// means for storing subproblem result
unordered_map<string, bool> mp;
bool isScramble(string S1, string S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.length() != S2.length()) {
return false;
}
int n = S1.length();
// Empty strings are scramble strings
if (n == 0) {
return true;
}
// Equal strings are scramble strings
if (S1 == S2) {
return true;
}
// Check for the condition of anagram
string copy_S1 = S1, copy_S2 = S2;
sort(copy_S1.begin(), copy_S1.end());
sort(copy_S2.begin(), copy_S2.end());
if (copy_S1 != copy_S2) {
return false;
}
// make key of type string for search in map
string key = (S1 + " " + S2);
// checking if both string are before calculated or not
// if calculated means find in map then return it's
// value
if (mp.find(key) != mp.end()) {
return mp[key];
}
// declaring flag variable to store result
bool flag = false;
for (int i = 1; i < n; i++) {
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.substr(0, i), S2.substr(0, i))
&& isScramble(S1.substr(i, n - i),
S2.substr(i, n - i))) {
flag = true;
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.substr(0, i), S2.substr(n - i, i))
&& isScramble(S1.substr(i, n - i),
S2.substr(0, n - i))) {
flag = true;
return true;
}
}
// add key & flag value to map (store for future use)
// so next time no required to calculate it again
mp[key] = flag;
// If none of the above conditions are satisfied
return false;
}
// Driver Code
int main()
{
string S1 = "coder";
string S2 = "ocred";
if (isScramble(S1, S2)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java Program to check if a
// given string is a scrambled
// form of another string
import java.util.*;
public class Main
{
// map declaration for storing key value pair
// means for storing subproblem result
static HashMap<String, Boolean> mp = new HashMap<String, Boolean>();
static boolean isScramble(String S1, String S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.length() != S2.length()) {
return false;
}
int n = S1.length();
// Empty strings are scramble strings
if (n != 0) {
return true;
}
// Equal strings are scramble strings
if (S1 == S2) {
return true;
}
// Check for the condition of anagram
String copy_S1 = S1, copy_S2 = S2;
char[] t1 = copy_S1.toCharArray();
char[] t2 = copy_S2.toCharArray();
Arrays.sort(t1);
Arrays.sort(t2);
copy_S1 = new String(t1);
copy_S2 = new String(t2);
if (!copy_S1.equals(copy_S2)) {
return false;
}
// make key of type string for search in map
String key = (S1 + " " + S2);
// checking if both string are before calculated or not
// if calculated means find in map then return it's
// value
if (mp.containsKey(key)) {
return mp.get(key);
}
// declaring flag variable to store result
boolean flag = false;
for (int i = 1; i < n; i++) {
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.substring(0, i), S2.substring(0, i))
&& isScramble(S1.substring(i, n), S2.substring(i, n))) {
flag = true;
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.substring(0, i), S2.substring(n - i, n))
&& isScramble(S1.substring(i, n),
S2.substring(0, n - i))) {
flag = true;
return true;
}
}
// add key & flag value to map (store for future use)
// so next time no required to calculate it again
mp.put(key, flag);
// If none of the above conditions are satisfied
return false;
}
public static void main(String[] args) {
String S1 = "coder";
String S2 = "ocred";
if (isScramble(S1, S2)) {
System.out.print("Yes");
}
else {
System.out.print("No");
}
}
}
// This code is contributed by divyesh072019.
Python3
# Declaring unordered map globally
map={}
# Python3 program to check if a
# given string is a scrambled
# form of another string
def isScramble(S1: str, S2: str):
# Strings of non-equal length
# cant' be scramble strings
if len(S1) != len(S2):
return False
n = len(S1)
# Empty strings are scramble strings
if not n:
return True
# Equal strings are scramble strings
if S1 == S2:
return True
# Check for the condition of anagram
if sorted(S1) != sorted(S2):
return False
# Checking if both Substrings are in
# map or are already calculated or not
if(S1+' '+S2 in map):
return map[S1+' '+S2]
# Declaring a flag variable
flag = False
for i in range(1, n):
# Check if S2[0...i] is a scrambled
# string of S1[0...i] and if S2[i+1...n]
# is a scrambled string of S1[i+1...n]
if (isScramble(S1[:i], S2[:i]) and
isScramble(S1[i:], S2[i:])):
flag = True
return True
# Check if S2[0...i] is a scrambled
# string of S1[n-i...n] and S2[i+1...n]
# is a scramble string of S1[0...n-i-1]
if (isScramble(S1[-i:], S2[:i]) and
isScramble(S1[:-i], S2[i:])):
flag = True
return True
# Storing calculated value to map
map[S1+" "+S2] = flag
# If none of the above
# conditions are satisfied
return False
# Driver Code
if __name__ == "__main__":
S1 = "great"
S2 = "rgate"
if (isScramble(S1, S2)):
print("Yes")
else:
print("No")
C#
// C# Program to check if a
// given string is a scrambled
// form of another string
using System;
using System.Collections.Generic;
class GFG {
// map declaration for storing key value pair
// means for storing subproblem result
static Dictionary<string, bool> mp = new Dictionary<string, bool>();
static bool isScramble(string S1, string S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.Length != S2.Length) {
return false;
}
int n = S1.Length;
// Empty strings are scramble strings
if (n == 0) {
return true;
}
// Equal strings are scramble strings
if (S1 == S2) {
return true;
}
// Check for the condition of anagram
string copy_S1 = S1, copy_S2 = S2;
char[] t1 = copy_S1.ToCharArray();
char[] t2 = copy_S2.ToCharArray();
Array.Sort(t1);
Array.Sort(t2);
copy_S1 = new string(t1);
copy_S2 = new string(t2);
if (copy_S1 != copy_S2) {
return false;
}
// make key of type string for search in map
string key = (S1 + " " + S2);
// checking if both string are before calculated or not
// if calculated means find in map then return it's
// value
if (mp.ContainsKey(key)) {
return mp[key];
}
// declaring flag variable to store result
bool flag = false;
for (int i = 1; i < n; i++) {
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.Substring(0, i), S2.Substring(0, i))
&& isScramble(S1.Substring(i, n - i), S2.Substring(i, n - i))) {
flag = true;
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.Substring(0, i), S2.Substring(n - i, i))
&& isScramble(S1.Substring(i, n - i),
S2.Substring(0, n - i))) {
flag = true;
return true;
}
}
// add key & flag value to map (store for future use)
// so next time no required to calculate it again
mp[key] = flag;
// If none of the above conditions are satisfied
return false;
}
static void Main() {
string S1 = "coder";
string S2 = "ocred";
if (isScramble(S1, S2)) {
Console.Write("Yes");
}
else {
Console.Write("No");
}
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript Program to check if a
// given string is a scrambled
// form of another string
// map declaration for storing key value pair
// means for storing subproblem result
let mp = new Map();
function isScramble(S1, S2)
{
// Strings of non-equal length
// cant' be scramble strings
if (S1.length != S2.length) {
return false;
}
let n = S1.length;
// Empty strings are scramble strings
if (n == 0) {
return true;
}
// Equal strings are scramble strings
if (S1 == S2) {
return true;
}
// Check for the condition of anagram
let copy_S1 = S1, copy_S2 = S2;
let t1 = copy_S1.split('')
let t2 = copy_S2.split('')
t1.sort();
t2.sort();
copy_S1 = t1.join("");
copy_S2 = t2.join("");
if (copy_S1 != copy_S2) {
return false;
}
// make key of type string for search in map
let key = (S1 + " " + S2);
// checking if both string are before calculated or not
// if calculated means find in map then return it's
// value
if (mp.has(key)) {
return mp[key];
}
// declaring flag variable to store result
let flag = false;
for (let i = 1; i < n; i++) {
// Check if S2[0...i] is a scrambled
// string of S1[0...i] and if S2[i+1...n]
// is a scrambled string of S1[i+1...n]
if (isScramble(S1.substring(0, i), S2.substring(0, i))
&& isScramble(S1.substring(i, n),
S2.substring(i, n))) {
flag = true;
return true;
}
// Check if S2[0...i] is a scrambled
// string of S1[n-i...n] and S2[i+1...n]
// is a scramble string of S1[0...n-i-1]
if (isScramble(S1.substring(0, i), S2.substring(n - i, n))
&& isScramble(S1.substring(i, n),
S2.substring(0, n - i))) {
flag = true;
return true;
}
}
// add key & flag value to map (store for future use)
// so next time no required to calculate it again
mp[key] = flag;
// If none of the above conditions are satisfied
return false;
}
let S1 = "coder";
let S2 = "ocred";
if (isScramble(S1, S2)) {
document.write("Yes");
}
else {
document.write("No");
}
// This code is contributed by suresh07.
</script>
Producción
Yes
Complejidad de tiempo: O(N^2), donde N es la longitud de las strings dadas.
Espacio auxiliar: O (N ^ 2), ya que necesitamos almacenar la string O (N ^ 2) en nuestro mapa mp.
Publicación traducida automáticamente
Artículo escrito por amarjeet_singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA