Nhờ góp ý thuật toán bài ReverseParentheses trên Codefights

#1

Không biết sai trường hợp nào nhỉ .

Capture.PNG1275×735 85.4 KB

Code Java (SOLVED):

String reverseParentheses(String s) {
         while(s.indexOf("(") != (-1)){
            int end = s.indexOf(")");
            int begin = s.substring(0, end+1).lastIndexOf("(");
            String t = reverse(s.substring(begin + 1, end));
            s = s.substring(0,begin) + t + s.substring(end+1,s.length());
        }
        return s;
}
public static String reverse(String s){
    return new StringBuffer(s).reverse().toString();
}
1 Like
#2

Trường hợp này:

a((ac)(ab))

Nôm na là có vài cặp () đồng cấp nhau như trên là tạch.

2 Likes
#3

thế phải dùng stack à bác?

#4

Mình cũng nghĩ tới hướng dùng stack :smiley:
Nhưng đang nghiệm cách khác xem đc ko.

1 Like
#5

Kiểm tra xem có 2 hoặc nhiều ngoặc sát nhau không. Có thì đảo ngược từ trong ra ngoài

#6

Cách dễ nhất là duyệt chuỗi từ trái sang phải hễ cứ gặp “)” thì đảo chuỗi trước nó tính đến “(” gần nó nhất rồi lại duyệt lại cả chuỗi từ đầu. Có ai có cách nào khác không

1 Like
#7

@.@ đã sửa code lại cho bao cái trường hợp đó nhưng mà vẫn fail

#8

Mình cũng thử làm. Vì chưa học Java nên không viết bằng Java được, tuy mình viết bằng Python nhưng hơi dài :3 Trình còn kém. Mình lấy ý tưởng là thuật toán Reverse Polish Notation, bạn có dùng thì thay tên hàm rp_process thành reverseParentheses là được :3
http://ideone.com/5k7mAd (có sửa lại tí cho nó đúng với mấy cái case :joy:)

1 Like
#9

Ko rõ th này có tính là 1 case hay ko. Nhưng cho 1 dấu mở mà ko dấu đóng thì bị quăng exception.
(a(bc)d)(ef)(

1 Like
#10

ok cảm ơn nhiều nhé để tham khảo :wink:

#11

Cái đề nó đã đảm bảo là chuỗi nằm trong một ngoặc hợp lệ rồi tức là có mở có đóng ấy, câu cuối. Sau một hổi kiểm tra lại đề thì thấy là thuật toán của mình đã thay hết các ký tự space của chuỗi s ban đầu :joy: đã fix được rồi. Cảm ơn mọi người.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?