字符串替换

字符串替换

题目详情

给定一个字符串，仅由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。

package Test;public class CharReplace { public static void main(String[] args) { String s = new String("aa "); System.out.println(minLength(s)); } public static int minLength(String s) { s = s.replace(" ", ""); if (SoleString(s) == 0) return s.length(); while (s.length() > 2) s = Replace(s); s = Replace(s); System.out.println(s); return s.length(); } /** * 按照规则替换 * * @param s * @return */ public static String Replace(String s) { s = s.replace("ac", "b"); s = s.replace("ca", "b"); s = s.replace("ab", "c"); s = s.replace("ba", "c"); s = s.replace("bc", "a"); s = s.replace("cb", "a"); s = s.replace("aaa", "a"); s = s.replace("bbb", "b"); s = s.replace("ccc", "c"); return s; } /** * 判定初始字符串是否为单一字母 * * @param s * @return */ public static int SoleString(String s) { int k = 0; for (int i = 1; i < s.length(); i++) if (s.charAt(i) == s.charAt(i - 1)) k = 0; else { k = 1; break; } return k; }}

心得:

在我最开始做这道题之前 我总结了几个规律

1:字符串的最后结果 肯定是只有一种字母

1: 所有的字符串 最后的长度要么是1要么是2  (因为aaa的上一步可以是bcaa 要是换第一对就成为了aaa  但是我们可以换第二部分就成为了 bba然后 bc 然后a)

但我忽略了一个事实 那就是 如果初始字符串就是一串 单一字母呢?  不能替换!!!

直接返回 length

另外

while (s.length() > 2) s = Replace(s); s = Replace(s);

我替换了两次 为什么呢?

因为 一旦replace 替换完之后  结果是ab 我们应该继续往下走 再替换 问题是 s.length()>2

所以在循环外面 得再加一个替换

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。