Hackerrank字符串縮減

-5

我正在處理以下問題https://www.hackerrank.com/challenges/reduced-string。Hackerrank字符串縮減

我想遞歸解決上述問題。我的代碼如下。

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 
    public static void main(String[] args) throws Exception { 
     BufferedReader br = new BufferedReader(neInputStreamReader(System.in)); 
     String line = br.readLine(); 
     System.out.print(reduce(line)); 
    } 

    public static String reduce (String str) { 
     if (str.equals("")) return "Empty String"; 
     if (str.length()<2) return str; 
     if (str.charAt(0) == str.charAt(1)) return reduce(str.substring(2)); 
     return str.charAt(0) + reduce(str.substring(1)); 
    } 
}

上面的代碼失敗以下測試用例
BAAB

可以在任何一個指出什麼是我的代碼的問題？

來源

2016-09-26 Learner

可能重複[什麼是調試器，它如何幫助我診斷問題？]（http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-幫助我診斷問題） – Raedwald

這不是一個調試網站。 – sashas

**不起作用**如果您希望我們爲您提供幫助，則說明不夠完整。 – GhostCat

您的問題是：

reduce("baab") = 'b' + reduce("aab") = 'b' + reduce("b") = 'b' + 'b' = "bb"

你只能看你的第一個字符，直到你能不能馬上再刪除它。然後你再也不會再看它，即使在某個時候你實際上可以刪除它。

我想你可以做這樣的事情，而不是：

public static String reduce(String str){ 
    if(str.equals("")) 
     return "Empty String"; 
    if(str.length()<2) 
     return str; 
    if(str.charAt(0)==str.charAt(1)) 
     return reduce(str.substring(2)); 

    String rest = str.substring(1); 
    String reducedRest = reduce(rest); 

    if (rest.equals(reducedRest)) 
     return str; 
    else 
     return reduce(str.charAt(0) + reducedRest); 
}

這不是很大，但它應該告訴你的總體思路。現在，如果您不更改其餘部分，則只會忽略第一個字符。如果你確實改變了它，你需要再看一遍。

來源

2016-09-26 08:55:44 Mark

謝謝@mark – Learner

請記住，這不是最有效的方法。如果reducedRest實際上是一個減少的休息（意思是它減少了），那麼在技術上你只需要看看你的前兩個字符現在是否可以被刪除。但是否可以刪除它們，實際上不需要重新檢查剩餘的字符串。 – Mark

str.charAt(0)+reduce(str.substring(1));

如果charAt(0)成爲與str.substring(1)的第一個字符相等？你完成一個未減少的一對。

來源

2016-09-26 08:51:37

Hackerrank字符串縮減

回答

相關問題