Функция для удаления повторяющихся символов в строке

Ответ 1

Функция отлично выглядит для меня. Я написал встроенные комментарии. Надеюсь, это поможет:

// function takes a char array as input.
// modifies it to remove duplicates and adds a 0 to mark the end
// of the unique chars in the array.
public static void removeDuplicates(char[] str) {
  if (str == null) return; // if the array does not exist..nothing to do return.
  int len = str.length; // get the array length.
  if (len < 2) return; // if its less than 2..can't have duplicates..return.
  int tail = 1; // number of unique char in the array.
  // start at 2nd char and go till the end of the array.
  for (int i = 1; i < len; ++i) { 
    int j;
    // for every char in outer loop check if that char is already seen.
    // char in [0,tail) are all unique.
    for (j = 0; j < tail; ++j) {
      if (str[i] == str[j]) break; // break if we find duplicate.
    }
    // if j reachs tail..we did not break, which implies this char at pos i
    // is not a duplicate. So we need to add it our "unique char list"
    // we add it to the end, that is at pos tail.
    if (j == tail) {
      str[tail] = str[i]; // add
      ++tail; // increment tail...[0,tail) is still "unique char list"
    }
  }
  str[tail] = 0; // add a 0 at the end to mark the end of the unique char.
}

Ответ 2

Ваш код, извините, очень C-like.

Java String не является char[]. Вы говорите, что хотите удалить дубликаты из String, но вместо этого вы берете char[].

Является ли это char[] \0 -терминатом? Не похоже, потому что вы берете целые .length массива. Но тогда ваш алгоритм пытается \0 -терминировать часть массива. Что произойдет, если в массивах нет дубликатов?

Ну, как написано, ваш код на самом деле бросает ArrayIndexOutOfBoundsException на последнюю строку! Для \0 нет места, потому что все слоты исчерпаны!

Вы можете добавить чек, чтобы не добавлять \0 в этом исключительном случае, но тогда как вы планируете использовать этот код? Вы планируете использовать strlen -подобную функцию для поиска первого \0 в массиве? А что будет, если их нет? (из-за уникального исключительного случая выше?).

Что произойдет, если исходный String/char[] содержит a \0? (что вполне правомерно на Java, кстати, см. JLS 10.9 Массив символов не является строкой)

Результат будет беспорядок, и все потому, что вы хотите сделать все C-like и на месте без какого-либо дополнительного буфера. Вы уверены, что вам действительно нужно это сделать? Почему бы не работать с String, indexOf, lastIndexOf, replace и всем API более высокого уровня String? Это слишком медленно, или вы только подозреваете, что это?

"Преждевременная оптимизация - это корень всех зол". Извините, но если вы даже не можете понять, что делает исходный код, то выяснение того, как он будет вписываться в большую (и беспорядочную) систему, будет кошмаром.

Мое минимальное предложение состоит в том, чтобы сделать следующее:

• Сделайте функцию и возвращает String, т.е. public static String removeDuplicates(String in)
• Внутренне работает с char[] str = in.toCharArray();
• Заменить последнюю строку на return new String(str, 0, tail);

Это использует дополнительные буферы, но, по крайней мере, интерфейс к остальной системе намного чище.

В качестве альтернативы вы можете использовать StringBuilder как таковой:

static String removeDuplicates(String s) {
    StringBuilder noDupes = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        String si = s.substring(i, i + 1);
        if (noDupes.indexOf(si) == -1) {
            noDupes.append(si);
        }
    }
    return noDupes.toString();
}

Обратите внимание, что это по существу тот же алгоритм, что и у вас, но гораздо чище и без так много маленьких угловых случаев и т.д.

Ответ 3

Учитывая следующий вопрос:

Введите код для удаления повторяющихся символов в строке без используя любой дополнительный буфер. ПРИМЕЧАНИЕ: Одна или две дополнительные переменные в порядке. Дополнительная копия массива отсутствует.

Поскольку одна или две дополнительные переменные прекрасны, но буфер не разрешен, вы можете имитировать поведение хэш-карты, используя целое число для хранения битов. Это простое решение работает на O (n), которое быстрее вашего. Кроме того, он не является концептуально сложным и на месте:

    public static void removeDuplicates(char[] str) {
        int map = 0;
        for (int i = 0; i < str.length; i++) {
            if ((map & (1 << (str[i] - 'a'))) > 0) // duplicate detected
                str[i] = 0;
            else // add unique char as a bit '1' to the map
                map |= 1 << (str[i] - 'a');
        }
    }

Недостатком является то, что дубликаты (которые заменены на 0) не будут помещены в конец массива str []. Однако это можно легко устранить, перейдя через массив в последний раз. Кроме того, целое число может содержать только обычные буквы.

Ответ 4

private static String removeDuplicateCharactersFromWord(String word) {

    String result = new String("");

    for (int i = 0; i < word.length(); i++) {
        if (!result.contains("" + word.charAt(i))) {
            result += "" + word.charAt(i);
        }
    }

    return result;
}

Ответ 5

Это моё решение.

Алгоритм в основном такой же, как в книге "Взлом интервью", откуда взято это упражнение, но я попытался немного его улучшить и сделать код более понятным:

public static void removeDuplicates(char[] str) {
        // if string has less than 2 characters, it can't contain
        // duplicate values, so there nothing to do
        if (str == null || str.length < 2) {
            return;
        }

        // variable which indicates the end of the part of the string 
        // which is 'cleaned' (all duplicates removed)
        int tail = 0;

        for (int i = 0; i < str.length; i++) {
            boolean found = false;

            // check if character is already present in
            // the part of the array before the current char
            for (int j = 0; j < i; j++) {
                if (str[j] == str[i]) {
                    found = true;
                    break;
                }
            }

            // if char is already present
            // skip this one and do not copy it
            if (found) {
                continue;
            }

            // copy the current char to the index 
            // after the last known unique char in the array
            str[tail] = str[i];
            tail++;
        }

        str[tail] = '\0';
    }

Одно из важных требований из книги - сделать это на месте (как в моем решении), что означает, что никакая дополнительная структура данных не должна использоваться в качестве помощника при обработке строки. Это повышает производительность, не тратя впустую память.

Ответ 6

char[] chars = s.toCharArray();
    HashSet<Character> charz = new HashSet<Character>();

    for(Character c : s.toCharArray() )
    {
        if(!charz.contains(c))
        {
            charz.add(c);
            //System.out.print(c);
        }
    }

    for(Character c : charz)
    {
        System.out.print(c);
    }

Ответ 7

public String removeDuplicateChar(String nonUniqueString) {
    String uniqueString = "";
    for (char currentChar : nonUniqueString.toCharArray()) {
        if (!uniqueString.contains("" + currentChar)) {
            uniqueString += currentChar;
        }
    }

    return uniqueString;
}

Ответ 8

public static void main (String [] args)
    {
        String s = "aabbbeeddsfre";//sample string
        String temp2="";//string with no duplicates
        HashMap<Integer,Character> tc = new HashMap<Integer,Character>();//create a hashmap to store the char's
        char [] charArray = s.toCharArray();
        for (Character c : charArray)//for each char
        {
            if (!tc.containsValue(c))//if the char is not already in the hashmap
                {
                    temp2=temp2+c.toString();//add the char to the output string
                    tc.put(c.hashCode(),c);//and add the char to the hashmap
                }
        }

        System.out.println(temp2);//final string
    }

вместо HashMap Я думаю, что мы можем использовать Set тоже.

Ответ 9

Я понимаю, что это вопрос Java, но поскольку у меня есть приятное решение, которое может вдохновить кого-то преобразовать это в Java, во что бы то ни стало. Также мне нравятся ответы, когда к общим проблемам доступны несколько языков.

Итак, вот решение Python, которое является O (n), а также поддерживает весь диапазон ASCII. Конечно, это не относится к "а" и "а" как к одному и тому же:

Я использую 8 x 32 бит в качестве хэш-карты:

Также ввод представляет собой строковый массив, использующий dedup (list ('some string'))

def dedup(str):
    map = [0,0,0,0,0,0,0,0]
    for i in range(len(str)):
        ascii = ord(str[i])
        slot = ascii / 32
        bit = ascii % 32
        bitOn = map[slot] & (1 << bit)
        if bitOn:
            str[i] = ''
        else:
            map[slot] |= 1 << bit

    return ''.join(str)

также более pythonian способ сделать это, используя набор:

def dedup(s):
    return ''.join(list(set(s)))

Ответ 10

Метод подстановки. Конкатенация выполняется с помощью .concat(), чтобы избежать выделения дополнительной памяти для левой и правой руки +. Примечание. Это удаляет даже повторяющиеся пробелы.

private static String withoutDuplicatesSubstringing(String s){

        for(int i = 0; i < s.length(); i++){
          String sub = s.substring(i+1);
          int index = -1;
          while((index = sub.toLowerCase().indexOf(Character.toLowerCase(s.charAt(i)))) > -1 && !sub.isEmpty()){
              sub = sub.substring(0, index).concat(sub.substring(index+1, sub.length()));
          }
          s = s.substring(0, i+1).concat(sub);
        }
        return s;
    }

Тестовый пример:

String testCase1 = "nanananaa! baaaaatmaan! batman!";

Вывод: na! btm

Ответ 11

Это было бы намного проще, если бы вы просто зациклились на массиве и добавили все новые символы в список, а затем извлекли этот список.

При таком подходе вам нужно перетасовать массив при его прохождении и, в конечном счете, переместить его в соответствующий размер в конце.

Ответ 12

    String s = "Javajk";
    List<Character> charz = new ArrayList<Character>();
    for (Character c : s.toCharArray()) {
        if (!(charz.contains(Character.toUpperCase(c)) || charz
                .contains(Character.toLowerCase(c)))) {
            charz.add(c);
        }
    }
     ListIterator litr = charz.listIterator();
   while (litr.hasNext()) {

       Object element = litr.next();
       System.err.println(":" + element);

   }    }

это приведет к удалению дубликата, если символ присутствует в обоих случаях.

Ответ 13

public class StringRedundantChars {
    /**
     * @param args
     */
    public static void main(String[] args) {

        //initializing the string to be sorted
        String sent = "I love painting and badminton";

        //Translating the sentence into an array of characters
        char[] chars = sent.toCharArray();

        System.out.println("Before Sorting");
        showLetters(chars);

        //Sorting the characters based on the ASCI character code. 
        java.util.Arrays.sort(chars);

        System.out.println("Post Sorting");
        showLetters(chars);

        System.out.println("Removing Duplicates");
        stripDuplicateLetters(chars);

        System.out.println("Post Removing Duplicates");
        //Sorting to collect all unique characters 
        java.util.Arrays.sort(chars);
        showLetters(chars);

    }

    /**
     * This function prints all valid characters in a given array, except empty values
     * 
     * @param chars Input set of characters to be displayed
     */
    private static void showLetters(char[] chars) {

        int i = 0;
        //The following loop is to ignore all white spaces
        while ('\0' == chars[i]) {
            i++;
        }
        for (; i < chars.length; i++) {
            System.out.print(" " + chars[i]);
        }
        System.out.println();
    }

    private static char[] stripDuplicateLetters(char[] chars) {

        // Basic cursor that is used to traverse through the unique-characters
        int cursor = 0;
        // Probe which is used to traverse the string for redundant characters
        int probe = 1;

        for (; cursor < chars.length - 1;) {

            // Checking if the cursor and probe indices contain the same
            // characters
            if (chars[cursor] == chars[probe]) {
                System.out.println("Removing char : " + chars[probe]);
                // Please feel free to replace the redundant character with
                // character. I have used '\0'
                chars[probe] = '\0';
                // Pushing the probe to the next character
                probe++;
            } else {
                // Since the probe has traversed the chars from cursor it means
                // that there were no unique characters till probe.
                // Hence set cursor to the probe value
                cursor = probe;
                // Push the probe to refer to the next character
                probe++;
            }
        }
        System.out.println();

        return chars;
    }
}

Ответ 14

public class RemoveDuplicateInString {
    public static void main(String[] args) {
        String s = "ABCDDCA";
        RemoveDuplicateInString rs = new RemoveDuplicateInString();
        System.out.println(rs.removeDuplicate(s));

    }

    public String removeDuplicate(String s) {
        String retn = null;
        boolean[] b = new boolean[256];

        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {

            if (b[ch[i]]) {
                ch[i]=' ';

            }

            else {
                b[ch[i]] = true;

            }
        }

        retn = new String(ch);
        return retn;

    }

}

Ответ 15

/* program to remove the duplicate character in string */
/* Author senthilkumar M*/

char *dup_remove(char *str) 
{
    int i = 0, j = 0, l = strlen(str);
    int flag = 0, result = 0;

    for(i = 0; i < l; i++) {
         result = str[i] - 'a';
         if(flag & (1 << result)) {
            */* if duplicate found remove & shift the array*/*
            for(j = i; j < l; j++) {
                  str[j] = str[j+1];
             }
             i--; 
             l--; /* duplicates removed so string length reduced by 1 character*/
             continue;
         }
         flag |= (1 << result);
     }
     return str;
}

Ответ 16

public class RemoveCharsFromString {

static String testcase1 = "No, I am going to Noida";
static String testcase2 = "goings";

public static void main(String args[])throws StringIndexOutOfBoundsException{
    RemoveCharsFromString testInstance= new RemoveCharsFromString();
    String result = testInstance.remove(testcase1,testcase2);
    System.out.println(result);
}

//write your code here
public String remove(String str, String str1)throws StringIndexOutOfBoundsException
    {   String result=null;


       if (str == null)
        return "";


    try
    {
     for (int i = 0; i < str1.length (); i++) 
    {


        char ch1=str1.charAt(i);
        for(int j=0;j<str.length();j++)
        {
            char ch = str.charAt (j);

        if (ch == ch1)
        {
        String s4=String.valueOf(ch);
        String s5= str.replaceAll(s4, "");
        str=s5;


        }
        }

    }
    }
    catch(Exception e)
    {

    }
    result=str;
    return result;
    }
 }

Ответ 17

public static void main(String[] args) {

    char[] str = { 'a', 'b', 'a','b','c','e','c' };

    for (int i = 1; i < str.length; i++) {
        for (int j = 0; j < i; j++) {
            if (str[i] == str[j]) {
                str[i] = ' ';
            }
        }

    }
    System.out.println(str);
}

Ответ 18

Используя guava, вы можете просто сделать что-то вроде Sets.newHashSet(charArray).toArray(); Если вы не используете какие-либо библиотеки, вы все равно можете использовать new HashSet<Char>() и добавить туда массив char.

Ответ 19

Улучшенная версия для использования битмаски для обработки 256 символов:

public static void removeDuplicates3(char[] str) 
{
  long map[] = new long[] {0, 0, 0 ,0};
  long one = 1;

  for (int i = 0; i < str.length; i++) 
  {
    long chBit = (one << (str[i]%64));
    int n = (int) str[i]/64;

    if ((map[n] & chBit ) > 0) // duplicate detected
        str[i] = 0;
    else // add unique char as a bit '1' to the map
        map[n] |= chBit ;
  }

  // get rid of those '\0's
  int wi = 1;
  for (int i=1; i<str.length; i++)
  {
    if (str[i]!=0) str[wi++] = str[i];
  }

  // setting the rest as '\0'
  for (;wi<str.length; wi++) str[wi] = 0;
}

Результат: "## 1!! ASDJasanwAaw.,;..] [, [] == - 0" == > "# 1! ASDJasnw.,;] [= - 0" (двойные кавычки не включены )

Ответ 20

Эта функция удаляет дубликат из строки inline. Я использовал С# в качестве языка кодирования, и дубликаты удалены inline

 public static void removeDuplicate(char[] inpStr)
        {
            if (inpStr == null) return;
            if (inpStr.Length < 2) return;

        for (int i = 0; i < inpStr.Length; ++i)
        {

            int j, k;
            for (j = 1; j < inpStr.Length; j++)
            {

                if (inpStr[i] == inpStr[j] && i != j)
                {
                    for (k = j; k < inpStr.Length - 1; k++)
                    {
                        inpStr[k] = inpStr[k + 1];
                    }
                    inpStr[k] = ' ';
                }
            }

        }


        Console.WriteLine(inpStr);

    }

Ответ 21

(Java) Избегайте использования Map, структуры данных списка:

private String getUniqueStr(String someStr) {
    StringBuilder uniqueStr = new StringBuilder();
            if(someStr != null) {
       for(int i=0; i <someStr.length(); i++)   {
        if(uniqueStr.indexOf(String.valueOf(someStr.charAt(i))) == -1)  {
            uniqueStr.append(someStr.charAt(i));
        }
       }
            }
    return uniqueStr.toString();
}

Ответ 22

public class RemoveRepeatedCharacters {

    /**
     * This method removes duplicates in a given string in one single pass.
     * Keeping two indexes, go through all the elements and as long as subsequent characters match, keep
     * moving the indexes in opposite directions. When subsequent characters don't match, copy value at higher index
     * to (lower + 1) index.
     * Time Complexity = O(n)
     * Space  = O(1)
     * 
     */
    public static void removeDuplicateChars(String text) {

        char[] ch = text.toCharArray();
        int i = 0; //first index
        for(int j = 1; j < ch.length; j++) {
            while(i >= 0 && j < ch.length && ch[i] == ch[j]) {
                i--;
                j++;
                System.out.println("i = " + i + " j = " + j);               

            }

            if(j < ch.length) {
                ch[++i] = ch[j];
            }

        }

        //Print the final string
        for(int k = 0; k <= i; k++)
            System.out.print(ch[k]);

    }

    public static void main(String[] args) {

        String text = "abccbdeefgg";
        removeDuplicateChars(text);

    }

}

Ответ 23

package com.java.exercise;

public class RemoveCharacter {

    /**
     * @param args
     */
    public static void main(String[] args) {
        RemoveCharacter rem = new RemoveCharacter();
        char[] ch=rem.GetDuplicates("JavavNNNNNNC".toCharArray());
        char[] desiredString="JavavNNNNNNC".toCharArray();
        System.out.println(rem.RemoveDuplicates(desiredString, ch));

    }
    char[] GetDuplicates(char[] input)
    {
        int ctr=0;
        char[] charDupl=new char[20];
        for (int i = 0; i <input.length; i++)
        {
            char tem=input[i];
            for (int j= 0; j < i; j++)
            {
                if (tem == input[j])
                {
                    charDupl[ctr++] = input[j];
                }

            }
        }


        return charDupl;
    }
     public char[] RemoveDuplicates(char[] input1, char []input2)
     {

         int coutn =0;
         char[] out2 = new char[10];
         boolean flag = false;
         for (int i = 0; i < input1.length; i++)
         {
             for (int j = 0; j < input2.length; j++)
             {

                     if (input1[i] == input2[j])
                     {
                         flag = false;
                         break;
                     }
                     else
                     {
                         flag = true;
                     }

             }
             if (flag)
             {
                 out2[coutn++]=input1[i];
                 flag = false;
             }
         }
         return out2;
     }
}

Ответ 24

Еще одно решение, кажется, наиболее кратким до сих пор:

private static String removeDuplicates(String s)
    {   
        String x = new String(s);

        for(int i=0;i<x.length()-1;i++)
            x = x.substring(0,i+1) + (x.substring(i+1)).replace(String.valueOf(x.charAt(i)), "");

        return x;
    }   

Ответ 25

Я написал фрагмент кода для решения проблемы. Я проверил с определенными значениями, получил требуемый результат.

Примечание. Это занимает много времени.

static void removeDuplicate(String s) {

    char s1[] = s.toCharArray();

    Arrays.sort(s1);                    //Sorting is performed, a to z
                //Since adjacent values are compared

    int myLength = s1.length;           //Length of the character array is stored here

    int i = 0;                          //i refers to the position of original char array
    int j = 0;          //j refers to the position of char array after skipping the duplicate values 

    while(i != myLength-1 ){

        if(s1[i]!=s1[i+1]){     //Compares two adjacent characters, if they are not the same
            s1[j] = s1[i];      //if not same, then, first adjacent character is stored in s[j]
            s1[j+1] = s1[i+1];  //Second adjacent character is stored in s[j+1]
            j++;                //j is incremented to move to next location
        }

        i++;                    //i is incremented
    }

    //the length of s is i. i>j

    String s4 = new String (s1);        //Char Array to String

    //s4[0] to s4[j+1] contains the length characters after removing the duplicate
    //s4[j+2] to s4[i] contains the last set of characters of the original char array

    System.out.println(s4.substring(0, j+1));

}

Не забудьте запустить мой код с помощью ваших входов. Спасибо.

Ответ 26

Это мое решение

public static String removeDup(String inputString){
    if (inputString.length()<2) return inputString;
    if (inputString==null) return null;
    char[] inputBuffer=inputString.toCharArray();
    for (int i=0;i<inputBuffer.length;i++){
        for (int j=i+1;j<inputBuffer.length;j++){
            if (inputBuffer[i]==inputBuffer[j]){
                inputBuffer[j]=0;
            }
        }
    }
    String result=new String(inputBuffer);
    return result;
}

Ответ 27

Ну, я придумал следующее решение. Имея в виду, что S и s не являются дубликатами. Также у меня есть только одно жесткое кодированное значение. Но код работает абсолютно нормально.

public static String removeDuplicate (String str)   {

    StringBuffer rev = new StringBuffer();  
    rev.append(str.charAt(0));

    for(int i=0; i< str.length(); i++)
    {
        int flag = 0;
        for(int j=0; j < rev.length(); j++)
        {
            if(str.charAt(i) == rev.charAt(j))
            {
                flag = 0;
                break;
            }
            else
            {
                flag = 1;
            }
        }
        if(flag == 1)
        {
            rev.append(str.charAt(i));
        }
    }

    return rev.toString();
}

Ответ 28

Я не мог понять логику решения, поэтому я написал свое простое решение:

  public static void removeDuplicates(char[] str) {

    if (str == null) return; //If the string is null return      
    int length = str.length; //Getting the length of the string
    if (length < 2) return; //Return if the length is 1 or smaller

    for(int i=0; i<length; i++){ //Loop through letters on the array

        int j;

        for(j=i+1;j<length;j++){ //Loop through letters after the checked letters (i) 

            if (str[j]==str[i]){ //If you find duplicates set it to 0

                str[j]=0;
            }
        }
    }
}

Ответ 29

A O (n) решение:

import java.util.*;
import java.io.*;

public class String_Duplicate_Removal
{

public static String duplicate_removal(String s)
    {
        if(s.length()<2)
            return s;

        else if(s.length()==2)
        {
            if(s.charAt(0)==s.charAt(1))
                s = Character.toString(s.charAt(0));
            return s;
        }

        boolean [] arr = new boolean[26];

        for(int i=0;i<s.length();i++)
        {

            if(arr[s.charAt(i)-'a']==false)
                arr[s.charAt(i)-'a']=true;

            else
            {
                s= ((new StringBuilder(s)).deleteCharAt(i)).toString();
                i--;
            }
        }
        return s;
    }   

    public static void main(String [] args)
    {
        String s = "abbashbhqa";
        System.out.println(duplicate_removal(s));
    }
}

Ответ 30

I решить аналогичное упражнение в книге: взломать интервью по кодированию используя рекурсию.

package crackingcodeinterview;

public class Exercise {

static String textString = "this is a random text of [email protected]#$%^(^452464156";

public static void main(String[] args) {

    filterLetters(0, "");
}

public static void filterLetters(int position, String letters) {
    if (position != textString.length()) {

        boolean p = false;

        for (int i = 0; i < letters.length(); i++) {
            if (letters.charAt(i) == textString.charAt(position)) {
                p = true;
                break;
            }
        }

        if (!p) {
            letters += textString.charAt(position);
        }
        position++;
        filterLetters(position, letters);
    } else {
        System.out.println(letters);
    }
  }
}

Другое решение с использованием подстроки и рекурсии

public class MyClass {
public static void main(String args[]) {

    getUnicLetter("esta es una cadena con letras repetidas","");
}



   public static String getUnicLetter(String originalWord,String finalWord){
        if(originalWord.isEmpty()) return  null;
        System.out.print(finalWord);
        return getUnicLetter(originalWord.replace(originalWord.substring(0,1),""),finalWord.contains(originalWord.substring(0,1)) ? "" : originalWord.substring(0,1));
    }

}