Een vriend van mij kreeg vandaag de volgende vraag tijdens een interview voor de functie van softwareontwikkelaar:
Gegeven twee strings s1en s2hoe ga je controleren of s1een geroteerdeversie is van s2?
Voorbeeld:
If s1 = "stackoverflow"dan zijn de volgende enkele van de gedraaide versies:
"tackoverflows"
"ackoverflowst"
"overflowstack"
waar als "stackoverflwo"geeneen gedraaide versie is.
Het antwoord dat hij gaf was:
Neem
s2en zoek het langste voorvoegsel dat een subreeks is vans1, dat je het rotatiepunt geeft. Zodra je dat punt hebt gevonden, breek jes2op dat punt oms2aens2bte krijgen, controleer dan ofconcatenate(s2a,s2b) == s1
Het lijkt mij en mijn vriend een goede oplossing. Maar de interviewer dacht daar anders over. Hij vroeg om een eenvoudigere oplossing. Help me alsjeblieft door te vertellen hoe je dit zou doen in Java/C/C++?
Bij voorbaat dank.
Antwoord 1, autoriteit 100%
Zorg er eerst voor dat s1en s2even lang zijn. Controleer vervolgens of s2een substring is van s1aaneengeschakeld met 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
In Java:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
Antwoord 2, autoriteit 15%
Een beter antwoord zou zeker zijn: “Nou, ik zou het de stackoverflow-community vragen en zou waarschijnlijk binnen 5 minuten minstens 4 echt goede antwoorden hebben”. Hersenen zijn goed en zo, maar ik zou meer waarde hechten aan iemand die weet hoe hij met anderen moet samenwerken om tot een oplossing te komen.
Antwoord 3, autoriteit 7%
Nog een python-voorbeeld (gebaseerd op HET antwoord):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
Antwoord 4, autoriteit 5%
Omdat anderen een kwadratische oplossing voor tijdcomplexiteit in het slechtste geval hebben ingediend, zou ik een lineaire toevoegen (gebaseerd op de KMP-algoritme):
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;
}
Antwoord 5, autoriteit 4%
EDIT: het geaccepteerde antwoord is duidelijk eleganter en efficiënter dan dit, als je het ziet. Ik liet dit antwoord achter als wat ik zou doen als ik er niet aan had gedacht de originele string te verdubbelen.
Ik zou het gewoon bruut forceren. Controleer eerst de lengte en probeer dan elke mogelijke rotatieoffset. Als geen van beide werkt, retourneer dan false – als een van hen wel werkt, retourneer dan onmiddellijk waar.
Het is niet specifiek nodig om samen te voegen – gebruik gewoon aanwijzers (C) of indexen (Java) en loop beide langs, één in elke reeks – beginnend bij het begin van een reeks en de huidige kandidaat-rotatie-offset in de tweede reeks, en inpakken waar nodig. Controleer op tekengelijkheid op elk punt in de tekenreeks. Als je aan het einde van de eerste reeks komt, ben je klaar.
Het zou waarschijnlijk ongeveer net zo gemakkelijk samen te voegen zijn, hoewel waarschijnlijk minder efficiënt, in ieder geval in Java.
Antwoord 6, autoriteit 2%
Hier is er een die regex gebruikt voor de lol:
boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
Je kunt het een beetje eenvoudiger maken als je een speciaal scheidingsteken kunt gebruiken dat gegarandeerd niet in beide tekenreeksen voorkomt.
boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
Je kunt in plaats daarvan ook lookbehind gebruiken met eindige herhaling:
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
Antwoord 7
Whoa, whoa… waarom is iedereen zo blij met een O(n^2)-antwoord? Ik ben er zeker van dat we het hier beter kunnen doen. HET bovenstaande antwoord omvat een O(n)-bewerking in een O(n)-lus (de substring/indexOf-aanroep). Zelfs met een efficiënter zoekalgoritme; zeg Boyer-Mooreof KMP, het slechtste geval is nog steeds O(n^2)met duplicaten.
Een O(n)gerandomiseerd antwoord is eenvoudig; neem een hash (zoals een Rabin-vingerafdruk) die een O(1)schuifvenster ondersteunt; hash string 1, dan hash string 2, en ga verder met het verplaatsen van het venster voor hash 1 rond de string en kijk of de hash-functies botsen.
Als we ons voorstellen dat het ergste geval zoiets is als “het scannen van twee DNA-strengen”, dan neemt de kans op botsingen toe, en dit degenereert waarschijnlijk tot iets als O(n^(1+e))of zoiets (hier gissen).
Eindelijk is er een deterministische O(nlogn)-oplossing met een zeer grote constante buiten. Kortom, het idee is om een convolutie van de twee snaren te nemen. De maximale waarde van de convolutie is het rotatieverschil (als ze worden geroteerd); een O(n)-controle bevestigt. Het leuke is dat als er twee gelijke max-waarden zijn, ze beide ook geldige oplossingen zijn. Je kunt de convolutie doen met twee FFT’s en een puntproduct, en een iFFT, dus nlogn + nlogn + n + nlogn + n == O(nlogn).
Omdat je niet met nullen kunt opvullen en je niet kunt garanderen dat de snaren 2^n lang zijn, zullen de FFT’s niet de snelle zijn; het zullen de langzame zijn, nog steeds O(nlogn)maar een veel grotere constante dan het CT-algoritme.
Dat gezegd hebbende, ik ben er absoluut 100% zeker van dat er hier een deterministische O(n)-oplossing is, maar verdorie als ik die kan vinden.
Antwoord 8
Zorg ervoor dat de twee snaren dezelfde lengte hebben. Dan kun je dit in C doen met een eenvoudige pointer-iteratie.
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);
}
Antwoord 9
Hier is een O(n)en een correct algoritme. Het gebruikt de operator <voor de elementen van de tekenreeksen. Het is natuurlijk niet van mij. Ik heb het overgenomen van hier(De site is in het Pools. Ik ben er in het verleden eens op gestuit en ik kon zoiets nu niet in het Engels vinden, dus ik laat het zien wat ik heb :)).
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;
}
Antwoord 10
Ik denk dat het beter is om dit in Javate doen:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
In Perl zou ik doen:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}
of nog beter de functie indexgebruiken in plaats van de regex:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
Antwoord 11
Niet zeker of dit de meest efficiënte methode is, maar het kan relatief interessantzijn: de Burrows-Wheeler-transformatie. Volgens het WP-artikel leveren alle rotaties van de invoer dezelfde uitvoer op. Voor toepassingen zoals compressie is dit niet wenselijk, dus de oorspronkelijke rotatie wordt aangegeven (bijvoorbeeld door een index; zie het artikel). Maar voor een eenvoudige rotatie-onafhankelijke vergelijking klinkt het ideaal. Het is natuurlijk niet per se ideaal efficiënt!
Antwoord 12
Neem elk teken als een amplitude en voer er een discrete Fourier-transformatie op uit. Als ze alleen door rotatie verschillen, zullen de frequentiespectra hetzelfde zijn tot binnen de afrondingsfout. Dit is natuurlijk inefficiënt tenzij de lengte een macht van 2 is, dus je kunt een FFT doen 🙂
Antwoord 13
Niemand heeft nog een modulo-aanpak aangeboden, dus hier is er een:
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "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;
}
Uitvoer:
A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False
A: stackoverflow 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: stackoverflow 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: stackoverflow 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: stackoverflow 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: 12-04-2010]
piotrheeft de fout in mijn bovenstaande code opgemerkt. Het fout wanneer het eerste teken in de tekenreeks twee keer of meer voorkomt. Bijvoorbeeld, stackoverflowgetest tegen owstackoverflowresulteerde in false, terwijl het waar zou moeten zijn.
Bedankt piotr voor het opsporen van de fout.
Hier is de gecorrigeerde code:
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("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "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
Dit is de uitvoer:
A: stackoverflow B: ztackoverflow
Rotation : False
A: stackoverflow 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: stackoverflow 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: stackoverflow 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: stackoverflow 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: stackoverflow 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
Dit is de lambda-aanpak:
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("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));
string strToTestFrom = "stackoverflow";
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
Hier is de output van de lambda-benadering:
Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True
Antwoord 14
Omdat niemand een C++-oplossing heeft gegeven. hier is het:
bool isRotation(string s1,string s2) {
string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
Antwoord 15
Opera’s simpele truc voor het draaien van de aanwijzer werkt, maar is in het ergste geval tijdens de looptijd uiterst inefficiënt. Stel je gewoon een string voor met veel lange herhalende reeksen karakters, dat wil zeggen:
S1 =
HELLOHELLOHELLO1HELLOHELLOHELLO2S2 =
HELLOHELLOHELLO2HELLOHELLOHELLO1
De “loop totdat er een mismatch is, verhoog dan met één en probeer het opnieuw” is een afschuwelijke benadering, rekenkundig.
Om te bewijzen dat je de aaneenschakelingsaanpak in gewone C zonder al te veel moeite kunt doen, hier is mijn oplossing:
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);
}
Dit is lineair in looptijd, ten koste van O(n)-geheugengebruik in overhead.
(Merk op dat de implementatie van strstr() platformspecifiek is, maar als het bijzonder hersendood is, kan het altijd worden vervangen door een sneller alternatief zoals het Boyer-Moore-algoritme)
Antwoord 16
C#:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
Antwoord 17
Ik hou van HET antwoord dat controleert of s2 een substring is van s1 aaneengeschakeld met s1.
Ik wilde een optimalisatie toevoegen die zijn elegantie niet verliest.
In plaats van de strings samen te voegen, kun je een join-weergave gebruiken (ik weet het niet voor andere talen, maar voor C++ biedt Boost.Range dergelijke weergaven).
Omdat de controle of een string een substring van een andere is, een lineaire gemiddelde complexiteit heeft (in het ergste geval is de complexiteit kwadratisch), zou deze optimalisatie de snelheid gemiddeld met een factor 2 moeten verbeteren.
Antwoord 18
Een puur Java-antwoord (zonder nulcontroles)
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;
}
Antwoord 19
En nu iets heel anders.
Als je een heel snel antwoord wilt in een beperkte context wanneer strings nietten opzichte van elkaar roteren
- bereken een op tekens gebaseerde controlesom (zoals het bepalen van alle tekens) op beide strings. Als handtekeningen verschillen, zijn strings geen rotaties van elkaar.
Akkoord, het kan mislukken, maar het is ergsnel om te zeggen of tekenreeksen niet overeenkomen en als ze overeenkomen, kunt u nog steeds een ander algoritme gebruiken, zoals tekenreeksaaneenschakeling om te controleren.
Antwoord 20
Een andere Ruby-oplossing gebaseerd op hetantwoord:
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
Antwoord 21
Het is heel gemakkelijk om in PHP te schrijven met de functies strlenen strpos:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
Ik weet niet wat strposintern gebruikt, maar of het KMPdit zal lineair zijn in de tijd.
Antwoord 22
Steek een van de snaren om. Neem de FFT van beide (behandel ze als eenvoudige reeksen gehele getallen). Vermenigvuldig de resultaten puntsgewijs met elkaar. Transformeer terug met behulp van inverse FFT. Het resultaat heeft een enkele piek als de snaren elkaars rotaties zijn — de positie van de piek geeft aan hoeveel ze ten opzichte van elkaar zijn gedraaid.
Antwoord 23
Waarom niet zoiets?
//is q a rotation of p?
bool isRotation(string p, string q) {
string table = q + q;
return table.IndexOf(p) != -1;
}
Natuurlijk kunt u uw eigen IndexOf()-functie schrijven; Ik weet niet zeker of .NET een naïeve of een snellere manier gebruikt.
Naïef:
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;
}
Sneller:
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;
}
Bewerken: ik heb misschien wat losse problemen; geen zin om te controleren. 😉
Antwoord 24
Ik zou dit doen in Perl:
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
Antwoord 25
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;
}
Antwoord 26
Voeg string1samen met string2en gebruik KMP-algoritmeom te controleren of string2aanwezig is in nieuw gevormde string. Omdat de tijdcomplexiteit van KMP kleiner is dan substr.