Алгоритм для удаления повторяющихся символов в Java

Question

Я работаю в program, что говорится, что

Существует строка, состоящая из строчных латинских букв алфавита. В одной операции мы можем удалить любую пару соседних букв с одинаковым значением.

Например, строка «aabcc» станет либо «aab», либо «bcc» после операции.

Результат должен быть как можно меньше. Чтобы сделать это, мы должны повторить вышеуказанную операцию столько раз, сколько она может быть выполнена.

Пример:

case 1: 

Input - aaabccddd 
Output - abd 

Здесь последовательность операций заключаются в следующем:

aaabccddd → abccddd 
abccddd → abddd 
abddd → abd 

Вы можете обратиться к ссылке выше для более подробной информации.

Я пытался использовать список, чтобы решить эту проблему, но я вижу, что это не правильный подход:

import java.util.Arrays; 
import java.util.List; 
import java.util.Scanner; 

public class Solution { 

    public static void main(String[] args) { 
     Scanner scan = new Scanner(System.in); 
     String data = scan.next(); 
     scan.close(); 

     String[] dataArr = data.split(""); 

     List<String> elements = Arrays.asList(data.split("")); 

     for(int i=0; i< elements.size()-1; i++) { 
      if(elements.get(i).equals(elements.get(i+1))) { 
       elements.remove(i); 
       elements.remove(i+1); 
      } 
     } 
     System.out.println(elements); 
    } 
} 

Я получаю ошибку как: java.lang.UnsupportedOperationException

Пожалуйста, помогите мне о том, что это правильный путь решите эту проблему.

Answer 1

Теперь, когда мы уже помогает слишком много, и спрашивающий имеет ACCPETED ответ, позвольте мне предложить свое решение:

StringBuilder result = new StringBuilder(input.length()); 
    for (int ix = 0; ix < input.length(); ix++) { 
     char ch = input.charAt(ix); 
     if (endsWith(ch, result)) { 
      removeLastChar(result); 
     } else { 
      result.append(ch); 
     } 
    } 
    String output = result.toString(); 

Я делаю все, что в один проход, и Я не думаю, что это становится слишком сложным (хотя это не решение с наименьшим количеством строк кода).

Я использую два вспомогательных метода:

private static boolean endsWith(char ch, StringBuilder buf) { 
    return buf.length() > 0 && buf.charAt(buf.length() - 1) == ch; 
} 

private static void removeLastChar(StringBuilder buf) { 
    buf.setLength(buf.length() - 1); 
} 

Answer 2

Arrays#asList создает неизменяемого списка, проверьте документы:

Возвращает фиксированного размера списка из подкрепленную указанного массива.

Вы не можете удалить элементы из него. Попробуйте:

List<String> elements = new ArrayList(Arrays.asList(data.split(""))); 

Answer 3

Maroun Maroun's answer описывает конкретную причину исключения в коде.

Простейшее решение, чем расщепление в списке перебирать строку символов мудрой:

StringBuilder sb = new StringBuilder(); 
int i = 0; 
while (i < str.length()) { 
    if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) { 
    i += 2; 
    } else { 
    sb.append(str.charAt(i)); 
    i += 1; 
    } 
} 
String result = sb.toString(); 

Answer 4

Наряду с исправлением по @MarounMaroun вы должны быть осторожны при удалении значений из списка вы находитесь итерации.

for(int i=0; i< elements.size()-1; i++) { 
    if(elements.get(i).equals(elements.get(i+1))) { 
     elements.remove(i); 
     elements.remove(i+1); // not the index you think it is 
    } 
} 

Поскольку удалить индекс i первый элемент вы думали в i+1 теперь сдвигается назад к i. Как правило, его проще удалять элементы дальше по списку до тех, которые ближе к началу.Вы могли бы написать:

for(int i=0; i< elements.size()-1; i++) { 
    if(elements.get(i).equals(elements.get(i+1))) { 
     elements.remove(i+1); 
     elements.remove(i); 
    } 
} 

Или вы могли бы написать:

for(int i=0; i< elements.size()-1; i++) { 
    if(elements.get(i).equals(elements.get(i+1))) { 
     elements.remove(i); 
     elements.remove(i); 
    } 
} 

Answer 5

Самый простой способ сделать это (как я решил вопрос в прошлый раз), чтобы использовать Regex

// Somehow read input and store it in a String input 
String regex = "(.)\\1"; 

Pattern r = Pattern.compile(regex); 
Matcher m = r.matcher(input); 
while (m.find()) { 
    input = m.replaceAll(""); 
    m = r.matcher(input); 
} 
// check length, do other things and print 

Спасибо @ OleV.V. для указания строки вытекающее ошибку