递归地从字符串中删除重复字符

Question

递归地从字符串中删除重复字符

4

我需要帮助弄清楚如何从一个字符串中递归地去除重复的字符，这是真正的问题所在。

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);
    }
}

- user647207

这是来自作业吗？如果是，请复制粘贴原始问题。 - Trevor Arjeski

你能说一下预期的结果是什么吗？是ABARC还是ABRC？如果这是作业，有什么限制，需要使用什么，不需要使用什么？ - user unknown

7个回答

2

递归处理的一般技巧是将所有变量转换为参数，并将所有赋值语句改为函数调用。对于更复杂的任务，您可能需要多个函数，但通常可以轻松地将每个循环转换为尾递归函数：

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

这里是一些去重代码，仅作为示例（虽然它不会像你的代码那样做同样的事情）

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])

- hugomg

0

我认为这更简单：

private static String removeDups(String input){
    if (input.length() <= 1) return input;
    if (input.charAt(0) == input.charAt(1))
        return removeDups(input.substring(1));
    else
        return input.charAt(0)+removeDups(input.substring(1));
}

- Manny

0

这个能帮到你吗？

    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();
    }

- James Jithin

0

in C:

/* @params:
* src  -- input string pointer. String to remove dups from.
* dest -- output string pointer. Passed in as empty string.  
* iter -- index from where duplicate removal starts. (0)
* ---------------------------------------------------------
* Purpose:  
* Removes duplicate characters from a string recursively. 
*/
void remove_Dups_recursively(char *src, char *dest, int iter){
  /* base case 1 --> empty or 1 letter string */
   if(strlen(src) <= 1){
       dest = src;
       return;
   }

  /* base case 2 --> reached end of string */
   if(iter == strlen(src)){
       return;
   }

  /* current 'iter' element has been encountered before */
   if(strchr(dest, src[iter]) == NULL){
       dest[strlen(dest)] = src[iter]; 
       iter++;
       remove_Dups_recursively(src, dest, iter);
   }

  /* current 'iter' element has not been encountered before */
   else{
       iter++;
       remove_Dups_recursively(src, dest, iter);
   }
}
/* EXAMPLE: AAABBABCCABA
 * OUTPUT: ABC    */

- Anant Ojha

0

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;
}

- HITANSU

0

如果这对某人有帮助的话...

public static String cleanDuplicateAdjacentChars(String string) {
    // STOPPER: String is 1 or 0 chars
    if(string.length() <= 1) return string;
    // If first char equals second char then return recursive of string minus first char
    if(string.charAt(0) == string.charAt(1)) return clearEqualChars(string.substring(1));
    // Else return first char + recursive of string minus first char
    return string.charAt(0) + clearEqualChars(string.substring(1));
}

- user22152473

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eng.Fouad · Accepted Answer

你可以这样做：

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"

今日免费次数已满, 请开通会员/明日再来

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"