01/10/2018, 08:17
[Codefights]Nhờ các bạn gop ý thuật toán bài ReverseParentheses
Không biết sai trường hợp nào nhỉ .
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();
}
Bài liên quan
Trường hợp này:
Nôm na là có vài cặp () đồng cấp nhau như trên là tạch.
Ideone.com
Ideone.com
Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.
thế phải dùng stack à bác?
Mình cũng nghĩ tới hướng dùng stack
Nhưng đang nghiệm cách khác xem đc ko.
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
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
@.@ đã sửa code lại cho bao cái trường hợp đó nhưng mà vẫn fail
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_processthànhreverseParentheseslà được :3http://ideone.com/5k7mAd (có sửa lại tí cho nó đúng với mấy cái case )
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)(ok cảm ơn nhiều nhé để tham khảo
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 đã fix được rồi. Cảm ơn mọi người.