descargar - java vs c++ diferencias

Pregunta de la entrevista: verifique si una cadena es una rotación de otra cadena

Question

A un amigo mío se le hizo la siguiente pregunta hoy en la entrevista para el puesto de desarrollador de software:

Dadas dos cadenas s1 y s2 ¿cómo verificará si s1 es una versión rotada de s2 ?

Ejemplo:

Si s1 = "stackoverflow" , las siguientes son algunas de sus versiones rotadas:

"tackoverflows"
"ackoverflowst"
"overflowstack"

donde como "stackoverflwo" no es una versión rotada.

La respuesta que dio fue:

Toma s2 y encuentra el prefijo más largo que es una cadena secundaria de s1 , que te dará el punto de rotación. Una vez que encuentre ese punto, rompa s2 en ese punto para obtener s2a y s2b , luego simplemente verifique si concatenate(s2a,s2b) == s1

Parece una buena solución para mí y para mi amigo. Pero el entrevistador pensó lo contrario. Pidió una solución más sencilla. Por favor, ayúdame diciendo cómo harías esto en Java/C/C++ ?

Gracias por adelantado.

Answer 1

¿Por qué no algo como esto?

//is q a rotation of p?
bool isRotation(string p, string q) {
    string table = q + q;    
    return table.IndexOf(p) != -1;
}

Por supuesto, podrías escribir tu propia función IndexOf (); No estoy seguro de si .NET utiliza una forma ingenua o más rápida.

Ingenuo:

int IndexOf(string s) {
    for (int i = 0; i < this.Length - s.Length; i++)
        if (this.Substring(i, s.Length) == s) return i;
    return -1;
}

Más rápido:

int IndexOf(string s) {
    int count = 0;
    for (int i = 0; i < this.Length; i++) {
        if (this[i] == s[count])
            count++;
        else
            count = 0;
        if (count == s.Length)
            return i - s.Length;
    }
    return -1;
}

Edit: podría tener algunos problemas off-by-one; no tengo ganas de comprobar ;)

Answer 2

Aquí hay una O(n) y un algoritmo de posición. Utiliza el operador < para los elementos de las cuerdas. No es mío, por supuesto. Lo tomé de here (el sitio está en polaco. Lo encontré una vez en el pasado y no pude encontrar algo así ahora en inglés, así que muestro lo que tengo :)).

bool equiv_cyc(const string &u, const string &v)
{
    int n = u.length(), i = -1, j = -1, k;
    if (n != v.length()) return false;

    while( i<n-1 && j<n-1 )
    {
        k = 1;
        while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
        if (k>n) return true;
        if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
    }
    return false;
}

Answer 3

Aquí hay uno que usa regex solo por diversión:

boolean isRotation(String s1, String s2) {
   return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)//2//1");
}

Puede hacerlo un poco más simple si puede usar un carácter de delimitador especial que no esté en ninguna de las cadenas.

boolean isRotation(String s1, String s2) {
   // neither string can contain "="
   return (s1 + "=" + s2).matches("(.*)(.*)=//2//1");
}

En su lugar, también puedes usar lookbehind con repetición finita:

boolean isRotation(String s1, String s2) {
   return (s1 + s2).matches(
      String.format("(.*)(.*)(?<=^.{%d})//2//1", s1.length())
   );
}

Answer 4

Como nadie ha dado una solución de C ++. aquí está:

bool isRotation(string s1,string s2) {

  string temp = s1;
  temp += s1;
  return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}

Answer 5

Como otros han presentado una solución de complejidad de tiempo en el peor de los casos cuadrática, agregaría una lineal (basada en el algoritmo KMP ):

bool is_rotation(const string& str1, const string& str2)
{
  if(str1.size()!=str2.size())
    return false;

  vector<size_t> prefixes(str1.size(), 0);
  for(size_t i=1, j=0; i<str1.size(); i++) {
    while(j>0 && str1[i]!=str1[j])
      j=prefixes[j-1];
    if(str1[i]==str1[j]) j++;
    prefixes[i]=j;
  }

  size_t i=0, j=0;
  for(; i<str2.size(); i++) {
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }
  for(i=0; i<str2.size(); i++) {
    if(j>=str1.size()) return true;
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }

  return false;
}

ejemplo de trabajo

Answer 6

DO#:

s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)

Answer 7

EDITAR: La respuesta aceptada es claramente más elegante y eficiente que esta, si la encuentra. Dejé esta respuesta como lo que haría si no hubiera pensado en duplicar la cadena original.

Yo sólo lo forzaría bruscamente. Verifique primero la longitud y luego intente todos los desplazamientos de rotación posibles. Si ninguno de ellos funciona, devuelva falso; si alguno de ellos lo hace, devuelva verdadero inmediatamente.

No hay necesidad particular de concatenar, solo use punteros (C) o índices (Java) y camine ambos a lo largo, uno en cada cadena, comenzando desde el principio de una cadena y el actual desplazamiento de desplazamiento candidato en la segunda cadena, y ajuste cuando sea necesario . Compruebe la igualdad de caracteres en cada punto de la cadena. Si llegas al final de la primera cadena, habrás terminado.

Probablemente sería tan fácil de concatenar, aunque probablemente menos eficiente, al menos en Java.

Answer 8

El simple truco de rotación del puntero de Opera funciona, pero es extremadamente ineficiente en el peor de los casos en el tiempo de ejecución. Simplemente imagine una cadena con muchas series de caracteres repetitivas largas, es decir:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

El "bucle hasta que haya una falta de coincidencia, luego el incremento en uno y vuelva a intentarlo" es un enfoque horrible, computacionalmente.

Para demostrar que puede hacer el enfoque de concatenación en C simple sin demasiado esfuerzo, aquí está mi solución:

  int isRotation(const char* s1, const char* s2) {
        assert(s1 && s2);

        size_t s1Len = strlen(s1);

        if (s1Len != strlen(s2)) return 0;

        char s1SelfConcat[ 2 * s1Len + 1 ];

        sprintf(s1SelfConcat, "%s%s", s1, s1);   

        return (strstr(s1SelfConcat, s2) ? 1 : 0);
}

Esto es lineal en el tiempo de ejecución, a expensas del uso de memoria O (n) en gastos generales.

(Tenga en cuenta que la implementación de strstr () es específica de la plataforma, pero si en particular tiene muerte cerebral, siempre se puede reemplazar con una alternativa más rápida como el algoritmo de Boyer-Moore)

Answer 9

Es muy fácil escribir en PHP usando las funciones strlen y strpos :

function isRotation($string1, $string2) {
    return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}

No sé qué strpos utiliza internamente, pero si utiliza KMP, esto será lineal en el tiempo.

Answer 10

Haría esto en Perl :

sub isRotation { 
     return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1; 
}

Answer 11

Invertir una de las cuerdas. Tome la FFT de ambos (tratándolos como secuencias simples de números enteros). Multiplica los resultados de manera puntual. Transformar de nuevo utilizando FFT inversa. El resultado tendrá un solo pico si las cuerdas son rotaciones entre sí; la posición del pico indicará por cuánto se giran entre sí.

Answer 12

Me gusta LA respuesta que verifica si s2 es una subcadena de s1 concatenada con s1.

Quería agregar una optimización que no pierda su elegancia.

En lugar de concatenar las cadenas, puede utilizar una vista de unión (no sé para otro idioma, pero para C ++ Boost.Range proporcione este tipo de vistas).

Como la verificación de si una cadena es una subcadena de otra tiene una complejidad promedio lineal (la complejidad del peor de los casos es cuadrática), esta optimización debería mejorar la velocidad en un factor de 2 en promedio.

Answer 13

Nadie ofreció un enfoque de módulo todavía, así que aquí hay uno:

static void Main(string[] args)
{
    Console.WriteLine("Rotation : {0}",
        IsRotation("", "ztackoverflow"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("", "ackoverflowst"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("", "overflowstack"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("", "stackoverflwo"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("", "tackoverflwos"));
    Console.ReadLine();
}

public static bool IsRotation(string a, string b)
{
    Console.WriteLine("/nA: {0} B: {1}", a, b);

    if (b.Length != a.Length)
        return false;

    int ndx = a.IndexOf(b[0]);
    bool isRotation = true;
    Console.WriteLine("Ndx: {0}", ndx);
    if (ndx == -1) return false;
    for (int i = 0; i < b.Length; ++i)
    {
        int rotatedNdx = (i + ndx) % b.Length;
        char rotatedA = a[rotatedNdx];

        Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );

        if (b[i] != rotatedA)
        {
            isRotation = false;
            // break; uncomment this when you remove the Console.WriteLine
        }
    }
    return isRotation;
}

Salida:

A:  B: ztackoverflow
Ndx: -1
Rotation : False

A:  B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A:  B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A:  B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False

A:  B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False

[EDIT: 2010-04-12]

piotr notó la falla en mi código de arriba. Se produce un error cuando el primer carácter de la cadena aparece dos veces o más. Por ejemplo, probado contra ow resultó falso, cuando debería ser verdadero.

Gracias piotr por detectar el error.

Ahora, aquí está el código corregido:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestRotate
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "ztackoverflow"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "ackoverflowst"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "stackoverflwo"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "tackoverflwos"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("", "owstackoverfl"));

            Console.ReadLine();
        }

        public static bool IsRotation(string a, string b)
        {
            Console.WriteLine("/nA: {0} B: {1}", a, b);

            if (b.Length != a.Length)
                return false;

            if (a.IndexOf(b[0]) == -1 )
                return false;

            foreach (int ndx in IndexList(a, b[0]))
            {
                bool isRotation = true;

                Console.WriteLine("Ndx: {0}", ndx);

                for (int i = 0; i < b.Length; ++i)
                {
                    int rotatedNdx = (i + ndx) % b.Length;
                    char rotatedA = a[rotatedNdx];

                    Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);

                    if (b[i] != rotatedA)
                    {
                        isRotation = false;
                        break;
                    }
                }
                if (isRotation)
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program
}//namespace TestRotate

Aquí está la salida:

A:  B: ztackoverflow
Rotation : False

A:  B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A:  B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A:  B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A:  B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A:  B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True

Aquí está el enfoque lambda:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsRotation
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "ztackoverflow"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("", "ackoverflowst"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("", "stackoverflwo"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("", "owstackoverfl"));

            string strToTestFrom = "";
            foreach(string s in StringRotations(strToTestFrom))
            {
                Console.WriteLine("is {0} rotation of {1} ? {2}",
                    s, strToTestFrom,
                    IsRotation(strToTestFrom, s) );
            }
            Console.ReadLine();
        }

        public static IEnumerable<string> StringRotations(string src)
        {
            for (int i = 0; i < src.Length; ++i)
            {
                var sb = new StringBuilder();
                for (int x = 0; x < src.Length; ++x)
                    sb.Append(src[(i + x) % src.Length]);

                yield return sb.ToString();
            }
        }

        public static bool IsRotation(string a, string b)
        {
            if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
            foreach(int ndx in IndexList(a, b[0]))
            {
                int i = ndx;
                if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program

}//namespace IsRotation

Aquí está la salida del enfoque lambda:

Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is  rotation of  ? True
is tackoverflows rotation of  ? True
is ackoverflowst rotation of  ? True
is ckoverflowsta rotation of  ? True
is koverflowstac rotation of  ? True
is overflowstack rotation of  ? True
is verflowstacko rotation of  ? True
is erflowstackov rotation of  ? True
is rflowstackove rotation of  ? True
is flowstackover rotation of  ? True
is lowstackoverf rotation of  ? True
is owstackoverfl rotation of  ? True
is wstackoverflo rotation of  ? True

Answer 14

No estoy seguro si este es el método más eficiente, pero podría ser relativamente interesante : la transformada de Burrows-Wheeler . De acuerdo con el artículo de WP, todas las rotaciones de la entrada producen la misma salida. Para aplicaciones como la compresión, esto no es deseable, por lo que se indica la rotación original (por ejemplo, mediante un índice; consulte el artículo). Pero para una comparación simple, independiente de la rotación, suena ideal. Por supuesto, no es necesariamente idealmente eficiente!

Answer 15

Otra solución de Ruby basada en the respuesta:

def rotation?(a, b); a.size == b.size and (b*2)[a]; end

Answer 16

Otro ejemplo de python (basado en la respuesta):

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

Answer 17

Primero asegúrese de que s1 y s2 sean de la misma longitud. Luego verifique si s2 es una subcadena de s1 concatenada con s1 :

algorithm checkRotation(string s1, string s2) 
  if( len(s1) != len(s2))
    return false
  if( substring(s2,concat(s1,s1))
    return true
  return false
end

En Java:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

Answer 18

Puño, asegúrese de que las 2 cuerdas tienen la misma longitud. Luego, en C, puedes hacer esto con una simple iteración de puntero.

int is_rotation(char* s1, char* s2)
{
  char *tmp1;
  char *tmp2;
  char *ref2;

  assert(s1 && s2);
  if ((s1 == s2) || (strcmp(s1, s2) == 0))
    return (1);
  if (strlen(s1) != strlen(s2))
    return (0);

  while (*s2)
    {
      tmp1 = s1;
      if ((ref2 = strchr(s2, *s1)) == NULL)
        return (0);
      tmp2 = ref2;
      while (*tmp1 && (*tmp1 == *tmp2))
        {
          ++tmp1;
          ++tmp2;
          if (*tmp2 == ''/0'')
            tmp2 = s2;
        }
      if (*tmp1 == ''/0'')
        return (1);
      else
        ++s2;
    }
  return (0);
}

Answer 19

Seguramente una mejor respuesta sería: "Bueno, le pediría a la comunidad de y probablemente tendría al menos 4 respuestas realmente buenas en 5 minutos". Los cerebros son buenos y todo, pero le daría un mayor valor a alguien que sabe cómo trabajar con otros para obtener una solución.

Answer 20

Supongo que es mejor hacer esto en Java :

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}

En Perl yo haría:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}

o incluso mejor usando la función de index lugar de la expresión regular:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}

Answer 21

Toma a cada personaje como una amplitud y realiza una transformada de Fourier discreta en ellos. Si difieren solo por la rotación, los espectros de frecuencia serán iguales al error de redondeo. Por supuesto, esto es ineficiente a menos que la longitud sea una potencia de 2 para que pueda hacer un FFT :-)

Answer 22

Una respuesta pura de Java (sin cheques nulos)

private boolean isRotation(String s1,String s2){
    if(s1.length() != s2.length()) return false;
    for(int i=0; i < s1.length()-1; i++){
        s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
        //--or-- s1 = s1.substring(1) + s1.charAt(0)
        if(s1.equals(s2)) return true;
    }
    return false;
}

Answer 23

Whoa, whoa ... ¿por qué todos están tan emocionados con una respuesta O(n^2) ? Estoy seguro de que podemos hacerlo mejor aquí. LA respuesta anterior incluye una operación O(n) en un bucle O(n) (la subcadena / llamada indexOf). Incluso con un algoritmo de búsqueda más eficiente; digamos Boyer-Moore o KMP , el peor de los casos sigue siendo O(n^2) con duplicados.

Una respuesta aleatoria O(n) es directa; tome un hash (como una huella digital de Rabin) que admita una ventana deslizante O(1) ; hash cadena 1, luego hash cadena 2, y procede a mover la ventana para hash 1 alrededor de la cadena y ver si las funciones hash chocan.

Si imaginamos que el peor de los casos es algo así como "escanear dos cadenas de ADN", la probabilidad de colisiones aumenta, y esto probablemente degenera en algo como O(n^(1+e)) o algo (solo adivinando aquí).

Finalmente, hay una solución determinista de O(nlogn) que tiene una constante exterior muy grande. Básicamente, la idea es tomar una convolución de las dos cuerdas. El valor máximo de la convolución será la diferencia de rotación (si se giran); una verificación O(n) confirma. Lo bueno es que si hay dos valores máximos iguales, entonces ambos también son soluciones válidas. Puede hacer la convolución con dos FFT y un producto de punto, y un iFFT, por lo que nlogn + nlogn + n + nlogn + n == O(nlogn) .

Como no puede rellenar con ceros y no puede garantizar que las cadenas tengan una longitud de 2 ^ n, las FFT no serán las rápidas; serán los lentos, aún O(nlogn) pero una constante mucho más grande que el algoritmo CT.

Dicho todo esto, estoy absolutamente seguro al 100% de que hay una solución O(n) aquí, pero, si puedo encontrarla, lo haré.

Answer 24

Y ahora para algo completamente diferente.

Si desea una respuesta realmente rápida en algún contexto restringido cuando las cadenas no son una rotación de otra

• calcular alguna suma de comprobación basada en caracteres (como xoring todos los caracteres) en ambas cadenas. Si las firmas difieren, las cadenas no son rotaciones unas de otras.

De acuerdo, puede fallar, pero es muy rápido decir si las cadenas no coinciden y si coinciden, puedes usar otro algoritmo como la concatenación de cadenas para verificar.

Answer 25

Unirse string1con string2y utilizar el algoritmo KMP para comprobar si string2está presente en la cadena recién formado. Porque la complejidad del tiempo de KMP es menor que substr.

Answer 26

int rotation(char *s1,char *s2)
{
    int i,j,k,p=0,n;
    n=strlen(s1);
    k=strlen(s2);
    if (n!=k)
        return 0;
    for (i=0;i<n;i++)
    {
        if (s1[0]==s2[i])
        {
            for (j=i,k=0;k<n;k++,j++)
            {
                if (s1[k]==s2[j])
                    p++;
                if (j==n-1)
                    j=0;
            }
        }
    }
    if (n==p+1)
      return 1;
    else
      return 0;
}