package com.boco.study; /** * 题目详情 给定一个字符串，仅由a,b,c 3种小写字母组成。 当出现连续两个不同的字母时，你可以用另外一个字母替换它，如 有ab或ba连续出现，你把它们替换为字母c； 有ac或ca连续出现时，你可以把它们替换为字母b； 有bc或cb 连续出现时，你可以把它们替换为字母a。 你可以不断反复按照这个规则进行替换，你的目标是使得最终结果所得到的字符串尽可能短， 求最终结果的最短长度。 输入：字符串。长度不超过200，仅由abc三种小写字母组成。 输出： 按照上述规则不断消除替换，所得到的字符串最短的长度。 例如：输入cab，输出2。因为我们可以把它变为bb或者变为cc。 输入bcab，输出1。尽管我们可以把它变为aab -> ac -> b，也可以把它变为bbb， 但因为前者长度更短，所以输出1。
*运行结果大于3秒，悲剧！ */
public class Main {
public static int minLength(String s){
s = Main.shortString(s);
System.out.println("返回的结果是："+s);
int length=s.length();
System.out.println("返回的大小是："+length);
return length;
}
public static String shortString(String s){
System.out.println(s);
String result="";
int length=s.length();
//String header="";
//如果最后剩下两个字符。
if(length==2)
{
//两个字符相同，无法再进行替换。
if(s.charAt(0)==s.charAt(1))
{
return s;
}else{
if(s.charAt(0)=='a'&&s.charAt(1)=='b')
{
return "c";
}else if(s.charAt(0)=='a'&&s.charAt(1)=='c'){
return "b";
}else if(s.charAt(0)=='b'&&s.charAt(1)=='a'){
return "c";
}else if(s.charAt(0)=='b'&&s.charAt(1)=='c'){
return "a";
}else if(s.charAt(0)=='c'&&s.charAt(1)=='a'){
return "b";
}else if(s.charAt(0)=='c'&&s.charAt(1)=='b'){
return "a";
}
}
}else if(length==1)
{
return s;
}else if(length>=3){
if(s.charAt(0)==s.charAt(1))
{
// header = s.charAt(0)+"";
s=s.charAt(0)+Main.shortString(s.substring(1));
if(s.charAt(0)==s.charAt(1)){
return s;
}else{
return Main.shortString(s);
}
}else{
if(s.charAt(0)=='a'&&s.charAt(1)=='b')
{
return Main.shortString("c"+s.substring(2));
}else if(s.charAt(0)=='a'&&s.charAt(1)=='c'){
return Main.shortString("b"+s.substring(2));
}else if(s.charAt(0)=='b'&&s.charAt(1)=='a'){
return Main.shortString("c"+s.substring(2));
}else if(s.charAt(0)=='b'&&s.charAt(1)=='c'){
return Main.shortString("a"+s.substring(2));
}else if(s.charAt(0)=='c'&&s.charAt(1)=='a'){
return Main.shortString("b"+s.substring(2));
}else if(s.charAt(0)=='c'&&s.charAt(1)=='b'){
return Main.shortString("a"+s.substring(2));
}
}
}
return result;
}
/**
* 参数：
* 1.操作的字符串。
* 函数内的变量:
* 1.当前滞留的字符串。（准确的说是新产生的字符串）。
* 2.当前操作的字符串的长度。
* 操作方法：
* 1.先比较下一个字符，如果不同，按照替换规则替换成新的字符串。接着执行替换函数。
* 2.如果相同。保留当前位置以前的字符串，将剩下的字符串继续执行替换函数。
* 3.将滞留的字符串的最后一个字符和返回的字符串进行相加，接着执行替换函数
* 循环结束的条件:
* 1.执行替换函数后返回的结果为1.
* 2.执行替换函数后返回的结果是2，但是两个字符相等。
* 返回的结果：
*
*/
public static void main(String[] args) {
String string="";
for(int i=0;i<200;i++)
{
if(i%3==0)
{
string+="a";
}else if(i%3==1){
string+="b";
}else if(i%3==2){
string+="c";
}
}
Main.minLength(string);
}
}