Algorithmus Hilfe wird benötigt (Codility)

Question

In diesem Problem betrachten wir nur Zeichenfolgen, die aus kleingeschriebenen englischen Buchstaben (a-z) bestehen. Eine Zeichenkette ist ein Palindrom, wenn sie von links nach rechts genau das gleiche liest wie von rechts nach links.

Zum Beispiel sind diese Strings Palindrome:

aza 
abba 
abacaba 

Diese Strings sind nicht Palindrome:

zaza 
abcd 
abacada 

ein String S der Länge N gegeben, eine Scheibe S ist ein Teilwort von S angegeben durch ein Paar von ganzen Zahlen (p, q), so dass 0 ≤ p < q < N. Eine Scheibe (p, q) der Saite S ist palindromisch, wenn die aus den Buchstaben S[p], S[p+1], ..., S[q] bestehende Saite ein Palindrom ist.

Zum Beispiel kann in einem String S = abbacada:

slice (0, 3) Palindrom ist, weil abba ein Palindrom ist,
Scheibe (6, 7) nicht palindromische weil da kein Palindrom ist,
slice (2, 5) ist nicht palindromisch, da baca kein Palindrom ist,
Scheibe (1, 2) ist palindrom, weil bb ein Palindrom ist.

---

Schreibe eine Funktion int solution(const string &S);, die eine Zeichenfolge S der Länge N Buchstaben angegeben, die Anzahl der Scheiben von palindromischen S. gibt die Funktion zurückgeben sollte -1, wenn diese Zahl größer als 100.000.000 ist.

Zum Beispiel für String S = baababa sollte die Funktion 6 zurückgeben, weil genau sechs ihrer Scheiben palindrom sind; nämlich: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Angenommen, dass:
- N ist eine ganze Zahl innerhalb des Bereichs [0..20.000];
- String S besteht nur aus Kleinbuchstaben (a-z).

Komplexität:
- erwartete Zeitkomplexität im ungünstigsten Fall ist O (N);
- Die erwartete Worst-Case-Raumkomplexität ist O (N) (ohne den für Eingabeargumente erforderlichen Speicher).

Hier ist meine Lösung:

int palindrom(const string &S, int startIndex,int endIndex, int counter=0) 
{ 
    bool equals = true; 
    if (endIndex - startIndex < 1) 
     return counter; 
    for(int i = startIndex,j = endIndex;i<j; ++i, --j) 
    { 
     equals = S[i] == S[j]; 
     if (!equals) break; 
    } 
    if (equals) counter++; 
    counter = palindrom(S,startIndex,endIndex-1,counter); 
    return counter; 
} 

int solution(const string &S) 
{ 
    int length = S.size(); 
    int counter = 0; 
    if (length > 20000) return -1; 
    for(int i=0; i < length-1; i++) 
    { 
     counter += palindrom(S,i,length-1); 
     if (counter > 100000000) return -1; 
    } 
    return counter; 
} 

mit großen Saiten S.size()> 3000 I erhalten Laufzeitfehler immer (bedeutet in weniger als 2 Sekunden Arbeitszeit mehr als 3 Sekunden, aber Lösung sollte)! Irgendwelche Vorschläge?

ok! und Hauptfunktion ist es so etwas wie:

main(){cout<<solution("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");} 

Answer 1

ich tun würde, ohne Rekursion

#include <string> 
#include <iostream> 

typedef std::string::const_iterator P; 

bool is_palindrom(P begin, P end) { 
    while (begin < end) { 
     if (*begin != *end) 
      return false; 
     ++begin; 
     --end; 
    } 
    return true; 
} 

int count_palindroms(const std::string &s) { 
    int c = 0; 
    P left = s.begin(); 
    while (left < s.end()) { 
     P right = left + 1; // because length palindrome > 1 
     while (right < s.end()) { 
      if (is_palindrom(left, right)) { 
       //std::cout << left - s.begin() << ' ' << right - s.begin() << std::endl; 
       c++; 
       if (c > 100000000) 
        return -1; 
      } 
      ++right; 
     } 
     ++left; 
    } 
    return c; 
} 

int main(int , char *[]) 
{ 
    std::cout << count_palindroms("baababa") << std::endl; 
    return 0; 
} 

Answer 2

Es funktioniert gut auf meinem PC. Was Sie hier eigentlich tun, ist, jede Unterzeichenfolge der ursprünglichen Zeichenfolge zu überprüfen und eine rekursive Funktion darüber auszuführen. Wie @PeterT erwähnt, erreichst du wahrscheinlich die maximale Tiefe deines steckengebliebenen.

Was ich tun würde, nicht den Call-Stack verwenden, sondern entweder verwenden, um meine eigenen stecken, oder ein paar einfache String-Funktionen verwenden wie:

std::string s = "aba"; 
std::string s1 = std::string(s.rbegin(), s.rend()); 
if (s == s1) 
{ 
///... 
} 

für ein Beispiel.

In Bezug auf die Zeit Komplexität - wie Sie here lesen können Sie nicht alle in o (n) überprüfen.

Answer 3

Ich würde einfach die Rekursion löschen (mit einer kleinen Änderung im Algorithmus):

int palindrom(const string &S, int startIndex, int endIndex, int counter = 0) 
{ 
    for (int k = endIndex; k > startIndex; --k) { 
     bool equals = true; 
     for (int i = startIndex, j = k; i < j; ++i, --j) 
      if (S[i] != S[j]) { 
       equals = false; 
       break; 
      } 
     if (equals) 
      counter++; 
    } 
    return counter; 
}