减少字符串

Question

我正在解决一个问题，将形式简化为不可简化的形式。这就是问题。

Shil has a string S , consisting of N lowercase English letters. In one operation, he can delete any pair of adjacent letters with same value. For example, string "aabcc" would become either "aab" or "bcc" after operation.

Shil wants to reduce S as much as possible. To do this, he will repeat the above operation as many times as it can be performed. Help Shil out by finding and printing 's non-reducible form!

If the final string is empty, print Empty String; otherwise, print the final non-reducible string.

Sample Input 0

aaabccddd

Sample Output 0

abd

Sample Input 1

baab

Sample Output 1

Empty String

Sample Input 2

aa

Sample Output 2

Empty String

说明

示例案例 0： Shil 可以执行以下操作序列以获得最终字符串：

因此，我们打印 .

示例案例 1： Shil 可以执行以下操作序列以获得最终字符串： aaabccddd -> abccddd

abccddd -> abddd

abddd -> abd

因此我们打印abd

示例案例 1： baab -> bb

bb -> 空字符串。

到目前为止我所做的是尝试通过 StringBuilder 解决它 Java.But 一些测试用例通过而其他测试用例没有通过，我无法找出错误是什么？

Here is the code that I have tried so far.

import java.util.Scanner;

public class Solution {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    StringBuilder sb = new StringBuilder(scan.nextLine());
    for(int i = 0; i < sb.length()-1; i++)
        {
            if(sb.charAt(i) == sb.charAt(i+1))
                sb.delete(i,i+2);
                i  = 0;
        }
    if(sb.length() == 0)
        System.out.println("Empty String");
    else
        System.out.println(sb.toString());
}

}

像 aaabccddd

这样的输入

和aa pass.But当输入是baab时失败。

Answer 1

问题是您只是运行循环字符串一次。例如：字符串 "baab"，你只需删除 "aa" 并完成循环。

解决方案：使用带有标志 isNonReducible 的递归，循环直到给出空字符串或标志 isNonReducible = true；

public class Solution {
public static StringBuilder checkReducible(StringBuilder sb) {
    boolean isNonReducible = true;
    for (int i = 0; i < sb.length() - 1; i++) {
        if (sb.charAt(i) == sb.charAt(i + 1)) {
            isNonReducible = false;
            sb.delete(i, i + 2);    
        }
    }
    if (sb.length() == 0) {
        return new StringBuilder("Empty String");
    }
    else {
        if(!isNonReducible) {
            sb = checkReducible(sb);
        }
        return sb; 
    }
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    StringBuilder sb = new StringBuilder(scan.nextLine());
    System.out.println(checkReducible(sb));
    scan.close();
}
}

Answer 2

你必须使用 while 循环。您的代码的问题在于它只遍历代码一次。在第一次迭代中，尽管您的输入 "baab" 变为 "bb"，然后它检查第二个 b 并尝试在 i+1 中找到 "b"（不存在）。将 for 循环更改为 while 循环，如下所示。

import java.util.Scanner;
public class Solution{
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    StringBuilder sb = new StringBuilder(scan.nextLine());
    int c=0;

    while(c< sb.length()-1){
        if(sb.charAt(c) == sb.charAt(c+1)){
            sb.delete(c,c+2);
            c=0;
        }
        else{
            c+=1;
        }
    }
    if(sb.length() == 0)
        System.out.println("Empty String");
    else
        System.out.println(sb.toString());
}

}

Answer 3

你可以在标签的帮助下试试这个，

 public static void main(String[] args) {
     boolean canReduce = true;
     Scanner scan = new Scanner(System.in);
     StringBuilder sb = new StringBuilder(scan.nextLine());


     startPoint: while (sb.length() > 0 && canReduce) {
        for (int i = 0; i < sb.length() - 1; i++) {
            if (sb.charAt(i) == sb.charAt(i + 1)) {
                sb.delete(i, i + 2);
                canReduce=true;
                 continue startPoint;
            }else{
                canReduce=false;
            }

        }
    }

    if (sb.length() == 0) {

        System.out.println("Empty String");
    } else {

        System.out.println(sb.toString());
    }
}

Answer 4

试试这个：

    public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    StringBuilder sb =new StringBuilder(in.nextLine());

   for (int i=0; i<sb.length()-1; i++){
        if(sb.charAt(i)==sb.charAt(i+1)){
            sb.delete(i, i+2);
            i=-1;

     }
    }
    if(sb.length()==0){
        System.out.println("Empty String");
    }else{
        System.out.println(sb);
    }
   }

减少字符串

To Reduce a String

java

string

stringbuilder