Tìm kiếm một chuỗi tối thiểu đáp ứng một số điều kiện

Question

Gần đây, tôi đã được hỏi vấn đề sau trong một cuộc phỏng vấn.

Cho một chuỗi S, tôi cần phải tìm một chuỗi S2 khác sao cho S2 là một dãy của S và S là một chuỗi S2 + ngược lại (S2). Ở đây '+' có nghĩa là nối. Tôi cần đưa ra độ dài tối thiểu có thể của S2 đối với S.

Tôi được cho biết đây là vấn đề lập trình động tuy nhiên tôi không thể giải quyết nó. Ai đó có thể giúp tôi với vấn đề này?

Edit-

Có cách nào để làm điều này trong thời gian O (N) hoặc ít hơn.

Answer 1

Mỗi ký tự từ S có thể được bao gồm trong S2 hay không. Với chúng tôi có thể xây dựng đệ quy mà cố gắng hai trường hợp:

• ký tự đầu tiên của S được sử dụng cho trang bìa,
• ký tự đầu tiên của S không phải là sử dụng cho trang bìa,

và tính toán tối thiểu hai bìa này. Để thực hiện điều này, nó là đủ để theo dõi bao nhiêu S được bao phủ với S2 đã được chọn ngược lại (S2).

Có tối ưu hóa mà chúng tôi biết kết quả là gì (bìa được tìm thấy, không thể có bìa) và không cần thiết phải có ký tự đầu tiên cho trang bìa nếu nó không bao hàm gì đó.

đơn giản thực hiện python:

cache = {} 

def S2(S, to_cover): 
    if not to_cover: # Covered 
     return '' 
    if not S:   # Not covered 
     return None 
    if len(to_cover) > 2*len(S): # Can't cover 
     return None 
    key = (S, to_cover) 
    if key not in cache: 
     without_char = S2(S[1:], to_cover)  # Calculate with first character skipped 
     cache[key] = without_char 
     _f = to_cover[0] == S[0] 
     _l = to_cover[-1] == S[0] 
     if _f or _l: 
      # Calculate with first character used 
      with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)]) 
      if with_char is not None: 
       with_char = S[0] + with_char # Append char to result 
       if without_char is None or len(with_char) <= len(without_char): 
        cache[key] = with_char 
    return cache[key] 

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132' 
c = S2(s, s) 
print len(s), s 
print len(c), c 

Answer 2

Hãy nói rằng S2 là "quả táo". Sau đó, chúng ta có thể làm cho giả thiết này:

S2 + reverseS2> = S> = S2
"appleelppa"> = S> = "quả táo"

Vì vậy, S sẽ cho một cái gì đó bao gồm cả "táo" để không nhiều hơn "appleelppe". Nó có thể là "appleel" hoặc "appleelpp".

String S ="locomotiffitomoc"; 
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank 
String S2 = ""; 
for (int a=0; a<S.length(); a++) { 
    try { 
     int b = 0; 
     while (S.charAt(a - b) == S.charAt(a + b + 1)) 
      b++; 
     // if this for loop breaks that means that there is a character that doesn't match the rule 
     // if for loop doesn't break but throws an exception we found it. 
    } catch (Exception e) { 
     // if StringOutOfBoundsException is thrown this means end of the string. 
     // you can check this manually of course. 
     S2 = S.substring(0,a+1); 
     break; 
    } 
} 
System.out.println(S2); // will print out "locomotif" 

Xin chúc mừng, bạn đã tìm thấy giá trị tối thiểu S2.

Answer 3

Có 2 khía cạnh quan trọng trong vấn đề này.

1. Vì chúng ta cần S làm chuỗi con của S2 + ngược (S2), S2 nên có ít nhất là n/2 chiều dài.
2. Sau khi nối của S2 và đảo ngược (S2), có một mô hình nơi các bảng chữ cái lặp đi lặp lại như

Vì vậy, giải pháp là để kiểm tra từ trung tâm của S đến cuối S cho bất kỳ yếu tố liên tiếp nào.Nếu bạn tìm thấy một thì hãy kiểm tra các phần tử ở hai bên như được hiển thị.

Bây giờ nếu bạn có thể tiếp cận đến hết chuỗi, sau đó số lượng tối thiểu của các yếu tố (kết quả) là khoảng cách từ đầu đến điểm mà bạn tìm thấy các yếu tố liên tiếp. Trong ví dụ này, C i.e 3.

Chúng tôi biết rằng điều này có thể không xảy ra luôn. tức là bạn không thể tìm thấy các yếu tố liên tiếp ở trung tâm. Hãy để chúng tôi nói rằng các yếu tố liên tiếp là sau khi trung tâm sau đó chúng tôi có thể làm cùng một thử nghiệm.

chuỗi Main

xâu

chuỗi Nối

Bây giờ đến t ông nghi ngờ lớn. Tại sao chúng ta chỉ xem xét phía bên trái bắt đầu từ trung tâm? Câu trả lời rất đơn giản, chuỗi nối được tạo bởi S + ngược (S). Vì vậy, chúng tôi chắc chắn rằng phần tử cuối cùng trong chuỗi con đến liên tiếp trong chuỗi được ghép nối. Không có cách nào mà bất kỳ sự lặp lại nào trong nửa đầu của chuỗi chính có thể cho kết quả tốt hơn vì ít nhất chúng ta phải có n bảng chữ cái trong chuỗi nối cuối cùng

Bây giờ vấn đề phức tạp: Tìm kiếm các chữ cái liên tiếp cho tối đa O (n) Bây giờ, việc kiểm tra các phần tử ở hai bên có thể làm cho trường hợp phức tạp nhất của O (n). nghĩa là so sánh tối đa n/2. Chúng ta có thể thất bại nhiều lần khi thực hiện lần kiểm tra thứ hai để chúng ta có một mối quan hệ nhân giữa sự phức tạp với O (n * n).

Tôi tin rằng đây là giải pháp đúng và chưa tìm thấy bất kỳ lỗ hổng nào.