*[topcoder]LittleElephantAndString

http://community.topcoder.com/stat?c=problem_statement&pm=12854&rd=15709

这道题DIV1 250的，还有点意思。看起来是O(n^2)的题，最后可以到O(n)。方法是从目标字符串的最后往前和原字符串逐个字符比较，匹配则比较下一个，不匹配则移动次数加一，只移动原字符串的index。原因是，首先字符串肯定能以n次转换成功，把目标串的最后一个第一个移动，直到第一个。这样找规律就可以发现，和目标顺序一样的可以不动。

import java.util.*;

public class LittleElephantAndString

{

    public int getNumber(String A, String B)

    {

        int len = A.length();

        char[] ac = A.toCharArray();

        char[] bc = B.toCharArray();

        Arrays.sort(ac);

        Arrays.sort(bc);

        for (int i = 0; i < len; i++) {

            if (ac[i] != bc[i])

                return -1;

        }

        int i = len - 1;

        int j = len - 1;

        int count = 0;

        while (i >= 0)

        {

            if (B.charAt(j) == A.charAt(i))

            {

                j--;

                i--;

            }

            else

            {

                count++;

                i--;

            }

        }

        return count;

    }

}

巴特西

*[topcoder]LittleElephantAndString

最新文章

热门文章