Giải quyết thử thách "chuỗi giảm"

Question

Tôi đã thấy nhiều cuộc thảo luận và nỗ lực mã khác nhau để giải quyết vấn đề "String reduction" từ interviewstreet.com, nhưng không ai trong số họ thực hiện nó thông qua lập trình động.

niêm yết dưới phần Dynamic Programming, vấn đề được mô tả như sau:

Cho một chuỗi gồm a, b và c, chúng ta có thể thực hiện các hoạt động sau đây: Lấy bất kỳ hai nhân vật riêng biệt liền kề và thay thế nó với nhân vật thứ ba. Ví dụ: nếu 'a' và 'c' liền kề, chúng có thể được thay thế bằng 'b'.

Chuỗi nhỏ nhất có thể là kết quả của việc áp dụng thao tác này nhiều lần?

Vấn đề có thể được giải quyết bằng thấu đáo tìm kiếm brute-force, tạo hiệu quả một cây của tất cả các thay thể:

// this is more or less pseudo code from my head 
int GetMinLength(string s) 
{ 
    // solve edge cases 
    if (s.Length == 1) return 1; 
    if (s.Length == 2) return ReduceIfPossible(s); 

    // recursive brute force 
    int min = s.Length; 
    for (int i = 0; i<s.Length-1; i++) 
    { 
     if (s[i] != s[i+1]) 
     { 
      var next = GetMinLength(
        s.Substring(0, i) + 
        Reduce(s[i], s[i + 1]) + 
        s.Substring(i + 2) 
       ); 

      if (next < min) min = next; 
     } 
    } 
} 

Điều này rõ ràng không cho lớn hơn N (N <= 100), vì vậy tôi đang cố gắng để phá vỡ nó thành các bài toán con nhỏ hơn, ghi nhớ chúng và kết hợp các kết quả.

Vấn đề là tôi không thể xác định trạng thái có "optimal substructure", cần thiết để áp dụng lập trình động (hoặc nói cách khác là "hợp nhất" kết quả từ các vấn đề phụ). Giảm thiểu một phần của chuỗi không đảm bảo rằng chuỗi cuối cùng sẽ thực sự là giải pháp nhỏ nhất.

Thuật ngữ "trạng thái" con trong trường hợp này có thể được hợp nhất vào giải pháp cuối cùng là gì?

Answer 1

Điều khiến bạn khó hiểu là bạn cần coi đây là 2 vấn đề lập trình động liên tiếp.

1. Tạo bảng, theo ký tự bạn kết thúc bằng vị trí bắt đầu, tất cả các vị trí cuối có thể là khối có thể được giảm xuống ký tự đó.
2. Độ dài nhỏ nhất có thể giảm xuống còn i ký tự cuối cùng của chuỗi. (Bảng mà bạn đã xây dựng ở bước 1 có thể được sử dụng để đệ quy giảm vấn đề này cho các bài toán con đã được giải quyết.)

Câu trả lời thứ hai cung cấp câu trả lời của bạn. Nó là đơn giản hơn nhiều nếu bạn đã giải quyết đầu tiên.

Answer 2

YOu bắt đầu bằng cách tạo cấu trúc mô tả lý thuyết giải pháp. Nó bao gồm số lượng nhân vật được xem xét, và chuỗi mã hóa cho đến nay, và một trường hợp xấu nhất và trường hợp tốt nhất cho lý thuyết.

Ban đầu chỉ có một lý thuyết - không có ký tự nào được xử lý. Trường hợp tốt nhất là chuỗi dài 1 (ví dụ: quy tắc luôn áp dụng và chuỗi có thể được giảm xuống một ký tự và trường hợp xấu nhất là N, trong đó không có quy tắc nào được áp dụng) Ví dụ:

encoded string = ""; 
encoded index = 0; 
worst case = N; 
best case = 1; 

Bây giờ, hãy bắt đầu tăng chỉ mục một và thêm ký tự vào chuỗi được mã hóa. Nếu không có quy tắc áp dụng, bạn giữ nguyên lý thuyết đó. Nếu quy tắc áp dụng, bạn có quyết định đưa ra - hoặc áp dụng quy tắc hoặc không. Vì vậy, khi bạn thêm một nhân vật bạn nhân đôi lý thuyết cho mỗi quy tắc có thể áp dụng cho ký tự cuối cùng và giữ một phiên bản không áp dụng quy tắc. Và bạn cập nhật trường hợp tốt nhất và trường hợp xấu nhất cho mỗi lý thuyết.

Lúc đầu, số lượng lý thuyết sẽ nhân lên rất nhanh. Nhưng cuối cùng bạn đến một tình huống mà trường hợp xấu nhất đối với một số lý thuyết là tốt hơn so với trường hợp tốt nhất cho các lý thuyết khác.

Vì vậy, bất cứ khi nào bạn tiến hành chỉ mục, bạn sẽ xóa các lý thuyết có trường hợp tốt nhất tệ hơn lý thuyết có trường hợp xấu nhất. Khi chỉ số tiếp cận N, hầu hết các lý thuyết sẽ bị loại bỏ. đang

Answer 3

Spoiler Alert:

public static int findMinReduction(String line){ 
    //Pseudocode: 
    //Count the number of occurences of each letter in the input string. 
    //If two of these counts are 0, then return string.length 
    //Else if (all counts are even) or (all counts are odd), then return 2 
    //Else, then return 1 

    int len = line.length(); 
    String a_reduce = line.replaceAll("c", "").replaceAll("b", ""); 
    String b_reduce = line.replaceAll("a", "").replaceAll("c", ""); 
    String c_reduce = line.replaceAll("a", "").replaceAll("b", ""); 

    int a_occurances = a_reduce.length(); 
    int b_occurances = b_reduce.length(); 
    int c_occurances = c_reduce.length(); 

    if ((a_occurances == b_occurances && a_occurances == 0) || 
     (a_occurances == c_occurances && a_occurances == 0) || 
     (b_occurances == c_occurances && b_occurances == 0)){ 
     return len; 
    } 
    else{ 
     if (a_occurances % 2 == 0 && 
      b_occurances % 2 == 0 && 
      c_occurances % 2 == 0){ 
      return 2; 
     } 
     if (a_occurances % 2 != 0 
      && b_occurances % 2 != 0 && 
      c_occurances % 2 != 0){ 
      return 2; 
     } 
    } 
    return 1; 
} 

phức tạp:

Đây là một O (n) thời gian hoạt động phức tạp, như đầu vào kích thước tăng lên, khối lượng công việc phải làm là tuyến tính với kích thước của đầu vào. Đó là sét nhanh chóng, chúng tôi có thể xử lý cho chuỗi có kích thước megabyte và vẫn xử lý chúng trong phân số của một giây.

Thuật toán tìm thấy ở đây với phân tích đầy đủ các lý do tại sao thuật toán này hoạt động:

stumped on a Java interview, need some hints