Pregunta de la entrevista: compruebe si una cadena es una rotación de otra cadena [cerrado]

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

Dadas dos cadenas s1, ¿ s2cómo comprobará si s1es una versión rotadas2 de ?

Ejemplo:

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

"tackoverflows"
"ackoverflowst"
"overflowstack"

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

La respuesta que dio fue:

Tome s2y encuentre el prefijo más largo que sea una subcadena de s1, que le dará el punto de rotación. Una vez que encuentre ese punto, rompa s2en ese punto para obtener s2ay s2b, luego simplemente verifique siconcatenate(s2a,s2b) == s1

Nos parece una buena solución a mí y a mi amigo. Pero el entrevistador pensó lo contrario. Pidió una solución más sencilla. Por favor ayúdame diciéndome ¿cómo harías esto Java/C/C++?

Gracias de antemano.

Mar 31 '10 20:03 Webdev

Primero asegúrate s1de que s2sean del mismo largo. Luego verifique si s2hay una subcadena s1concatenada 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);
}

Mar 31 '2010 13:03 codaddict

Seguramente una mejor respuesta sería: "Bueno, le preguntaría a la comunidad de stackoverflow y probablemente tendría al menos 4 respuestas realmente buenas en 5 minutos". El cerebro es bueno y todo eso, pero valoraría más a alguien que sepa cómo trabajar con otros para encontrar una solución.

Mar 31 '2010 20:03