Làm cách nào để xác định hiệu quả palindrome ký tự cá nhân dài nhất trong một chuỗi đã cho?

Question

Cho một chuỗi có độ dài N chứa ký tự [A-Z], làm cách nào để xác định palindrome dài nhất cho một ký tự riêng lẻ?

tôi sẽ minh họa điều này bằng một ví dụ:

chuỗi Given: JOHNOLSON Khi phân tích chuỗi, chúng ta thấy rằng chúng tôi có một palindrome với nhân vật O như vậy mà các chuỗi trông giống như JOHNOLSON. Các palindrome cho O 's là chiều dài 7 về cơ bản trông như O--O--O. Ngoài ra, hãy chú ý rằng có một palindrome với N, nhưng nó chỉ là chiều dài 6.

Một ví dụ khác, chuỗi Given: ABCJOHNOLSON cho kết quả tương tự như trên với một palindrome của O 's chiều dài 7 trông như O--O--O.

Tuy nhiên, với chuỗi cho trước ABCJOHNOLSONDA, dài nhất từng nhân vật palindrome là chiều dài 14 với nhân vật A trông như A------------A.

ví dụ đơn giản khác bao gồm:

ABA ->A-A (chiều dài 3)

ABAXYZ ->A-A (chiều dài 3)

ABAXYZA ->A---A (chiều dài 5), không dài 7 vì A-A---A không phải là một palindrome cho chữ A.

Đặc biệt chú ý đến ví dụ cuối cùng vì nó minh họa một trong những sắc thái tinh tế của vấn đề.

Answer 1

Bạn có thể làm điều đó trong thời gian tuyến tính, được mô tả here với mẫu mã.

Answer 2

Đây là những gì tôi nghĩ ra, tôi không biết hiệu quả của nó.

 
For every letter in the alphabet, 
    Find the first and last occurrence of this letter. 
    While the substring is not a palindrome for that letter (easy to check), 
    find the next letter on both sides so that every possible combination is 
    checked. Take the longest one and store it. 
Take the longest one. 

Answer 3

Chắc chắn không tối ưu. Giả sử chuỗi đầu vào là tất cả chữ thường.

using System; 
using System.Collections.Generic; 

public class LongestPalindrome 
{ 
    public int longest(string s) 
    { 
     Dictionary<char, List<int>> indices = 
      new Dictionary<char, List<int>>(); 

     // find all indices for each letter 
     for (int i = 0; i < s.Length; i++) 
     { 
      char c = s[i]; 
      if (!indices.ContainsKey(c)) 
        indices.Add(c, new List<int>()); 
      indices[c].Add(i); 
     } 

     int max = Int32.MinValue; 

     for (int i = (int)'a'; i <= (int)'z'; i++) 
     { 
      char c = (char)i; 

      // in case a letter didn't appear at all in the input string 
      if (!indices.ContainsKey(c)) continue; 

      List<int> indexList = indices[c]; 

      // in case a letter appeared only once in the input string 
      if (indexList.Count == 1) max = Math.Max(max, 1); 

      for (int j = 0; j < indexList.Count; j++) 
      { 
       for (int k = j + 1; k < indexList.Count; k++) 
       { 
        int dist = indexList[k] - indexList[j] + 1; 
        string sub = s.Substring(indexList[j], dist); 
        if (isPalendrome(sub, c)) 
             max = Math.Max(max, dist); 
       } 
      } 
     } 

     return max; 
    } 

    bool isPalendrome(string s, char c) 
    { 
     int i = 0; 
     while(i < s.Length - 1 - i) 
     { 
      if (s[i] != c && s[s.Length - 1 - i] != c) 
      { 
       i++; 
       continue; 
      } 
      if (s[i] != s[s.Length - 1 - i]) return false; 
      i++; 
     } 
     return true; 
    } 
}