Trợ giúp thuật toán là cần thiết (Mã hoá)

Question

Trong bài toán này, chúng tôi chỉ xem xét các chuỗi bao gồm các chữ cái viết hoa chữ thường (a − z). Một chuỗi là một palindrome nếu nó đọc chính xác giống nhau từ trái sang phải vì nó làm từ phải sang trái.

Ví dụ, những chuỗi là palindromes:

aza 
abba 
abacaba 

Các chuỗi này không palindromes:

zaza 
abcd 
abacada 

Cho một xâu S có độ dài N, một lát S là một chuỗi con của S quy định bởi một cặp số nguyên (p, q), chẳng hạn như 0 ≤ p < q < N. Một lát (p, q) của chuỗi S là palindromic nếu chuỗi chứa các chữ cái S[p], S[p+1], ..., S[q] là một palindrome.

Ví dụ, trong một chuỗi S = abbacada:

lát (0, 3) là xuôi ngược vì abba là một palindrome,
lát (6, 7) là không xuôi ngược vì da không phải là một palindrome,
lát (2, 5) không phải là palindromic vì baca không phải là palindrome,
lát (1, 2) là palindromic vì bb là palindrome.

---

Viết một hàm int solution(const string &S); rằng, Cho xâu S có độ dài N chữ cái, trả về số lát xuôi ngược của S. Chức năng nên trở về -1 nếu số này lớn hơn 100.000.000.

Ví dụ, đối với chuỗi S = baababa hàm sẽ trả về 6, vì chính xác sáu lát của nó là palindromic; cụ thể là: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Giả sử rằng:
- N là một số nguyên trong phạm vi [0,20,000];
- chuỗi S chỉ bao gồm các chữ thường (a − z).

Mức độ phức tạp:
- độ phức tạp thời gian xấu nhất dự kiến ​​là O (N);
- mức độ phức tạp của trường hợp xấu nhất được mong đợi là O (N) (không tính dung lượng cần thiết cho các đối số đầu vào).

Đây là giải pháp của tôi:

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; 
} 

với chuỗi lớn S.size()> 3000 tôi luôn luôn nhận được lỗi runtime (có nghĩa là thời gian là hơn sau đó 3 giây nhưng giải pháp nên làm việc trong ít hơn 2 giây)! Bất kỳ đề xuất?

ok! và chức năng chính là một cái gì đó như:

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

Answer 1

tôi sẽ làm mà không đệ quy

#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

Nó hoạt động tốt trên máy tính của tôi. Những gì bạn đang thực sự làm ở đây là kiểm tra mọi chuỗi con của chuỗi gốc và chạy một hàm đệ quy trên nó. Khi @PeterT đề cập đến bạn có thể đạt đến độ sâu tối đa của bạn bị mắc kẹt.

Những gì tôi sẽ làm là không sử dụng các cuộc gọi stack, nhưng một trong hai sử dụng gặp khó khăn của riêng mình, hoặc sử dụng một số chức năng chuỗi đơn giản như:

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

cho một ví dụ.

Về thời gian phức tạp - vì bạn có thể đọc here bạn không thể kiểm tra tất cả trong o (n).

Answer 3

tôi chỉ cần xóa các đệ quy (với một thay đổi nhỏ trong thuật toán):

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; 
}