從字符串中遞歸刪除重複字符

Question

我需要幫助來確定如何從字符串中刪除重複字符。它必須完成遞歸這是真正的問題..

public class FEQ2 { 
    /** 
    * @param args 
    */ 
    public static void removeDups(String s, int firstChar, int secondChar) {  
     if (s.length() == 1) { 
      System.out.println(s); 
     }   
     char a = s.charAt(firstChar); 
     if (a == s.charAt(secondChar)) { 
      s = a + s.substring(secondChar + 1); 
     } 
     System.out.println(s); 
     removeDups(s, firstChar + 1, secondChar + 1); 
     //return s; 
    } 

    public static void main(String[] args) { 
     //System.out.println(removeDups("AAAABBARRRCC", 1)); 
     removeDups("AAAABBARRRCC", 0 , 1); 
    } 
} 

Answer 1

你可以這樣說：

public static String removeDups(String s) 
{ 
    if (s.length() <= 1) return s; 
    if(s.substring(1,2).equals(s.substring(0,1))) return removeDups(s.substring(1)); 
    else return s.substring(0,1) + removeDups(s.substring(1)); 
} 


INPUT: "AAAABBARRRCC" 
OUTPUT: "ABARC" 

===============

編輯：另一種方式

public static String removeDups(String s) 
{ 
    if (s.length() <= 1) return s; 
    if(s.substring(1).contains(s.substring(0,1))) return removeDups(s.substring(1)); 
    else return s.substring(0,1) + removeDups(s.substring(1)); 
} 


INPUT: "AAAABBARRRCC" 
OUTPUT: "BARC" 

==============

編輯：3的方式

public static String removeDups(String s) 
{ 
    if (s.length() <= 1) return s; 
    if(s.substring(0,s.length()-1).contains(s.substring(s.length()-1,s.length()))) return removeDups(s.substring(0,s.length()-1)); 
    else return removeDups(s.substring(0,s.length()-1)) + s.substring(s.length()-1,s.length()); 
} 


INPUT: "AAAABBARRRCC" 
OUTPUT: "ABRC" 

Answer 2

遞歸做事的一般技巧是把所有的變量，並把它們變成參數，並改變所有分配到函數調用。您可能需要不止一個功能更復雜的東西，但通常你可以把每個循環爲tail-recursive功能很容易：

function(){ 
    int i=0; int x=0; //initialize 
    while(condition){ 
     x = x+i; //update 
     i = i+1; 
    } 
    return x; 
} 

成爲

function(i,x){ //variables are now parameters 
    if(condition){ 
     return x; 
    }else{ 
     return function(i+1, x+i); //update 
    } 
} 

main(){ 
    function(0,0); //initialize 

======== =======

下面是一些重複刪除代碼，只是舉例（它doesn't做同樣的事情，你雖然）

removeDuplicates(str): 
    i = str.length-1; out_str = ""; chars_used = [] 
    while(i >= 0): 
     c = str[i] 
     if(c not in chars_used): 
      chars_used.append(c) 
      out_str += c 
     i -= 1 
    return out_str 

成爲

remove_duplicates(str, i, out_str, chars_used): 
    if i < 0: 
     return out_str 
    else: 
     c = str[i] 
     if c in chars_used: 
      return remove_duplicates(str, i-1, out_str, chars_used) 
     else: 
      return remove_duplicates(str, i-1, out_str+c, chars_used+[c]) 

Answer 3

這能否幫助你？

public static String getUniqueChars(String realString) { 
     StringBuilder resultString = null; 
     try { 
       List<Character> characterArray = new <Character> ArrayList(); 
       for(char c : realString.toCharArray()) { 
        characterArray.add(c); 
       } 
       resultString = new StringBuilder(); 
       for(Character c : new TreeSet<Character>(characterArray)) { 
        resultString.append(c.charValue()); 
       } 
     } catch (Exception e) { 
       e.printStackTrace(); 
     } 
     resultString.toString(); 
    } 

Answer 4

private static String removeChars(String s) { 
    int n= s.length(); 
    int i= 0; 
    int j= 1; 
    Map<Integer, Boolean> mark= new HashMap<>(); 
    while(j<n) { 
     if(s.charAt(i)== s.charAt(j)) { 
      mark.put(i, true); 
      mark.put(j, true); 
      if(i== 0) { 
       i= j+1; 
       j= i+1; 
      } else { 
       i= i-1; 
       j= j+1; 
      } 
     } else { 
      i= j; 
      j= j+1; 
     } 
    } 

    String str= ""; 
    for(int k= 0;k<n;k++) { 
     if(!mark.containsKey(k)) { 
      str+= s.charAt(k); 
     } 
    } 
    return str; 
}