Codeforces Round #313 (Div. 2) D. Equivalent Strings

原题:http://codeforces.com/contest/560/problem/D

---

题目大意: 给字符串a和b, 定义a和b是等价的,如果:

1. a和b相等.
2. a等分成a1,a2,b等分成b1,b2, (a1==b1 && a2==b2) || (a2==b1 && a1==b2)

---

分析: 就暴呗…我也不知道为什么我暴就报错, 是因为java的原因么, 我看人家同样码用c++, 都飞快的.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        String a = in.readString();
        String b = in.readString();
        if (solve(a,b))
            out.print("YES");
        else
            out.print("NO");
    }
    private boolean solve(String a, String b) {
        if (a.length() % 2 != 0 || b.length() % 2 != 0)
            return a.equals(b);
        if (a.equals(b))
            return true;
        return (solve(a.substring(0, a.length() / 2), b.substring(0, b.length() / 2))
                && solve(a.substring(a.length() / 2, a.length()), b.substring(b.length() / 2, b.length())))
                || (solve(a.substring(0, a.length() / 2), b.substring(b.length() / 2, b.length()))
                && solve(a.substring(a.length() / 2, a.length()), b.substring(0, b.length() / 2)));
    }

---

答案的code是通过编码解的, 每次递归的时候, 都按照当前字符串的字典序排列列一下, 然后比较两个字符串是不是一样. 比如对cabddbac编码, 先递归到底, (c,a)(b,d)(d,b)(a,c),然后按照字典序排列(a,c)(b,d)(b,d)(a,c), 并且往上层走. (acbd)(acbd).最后就是acbdacbd

   public void solve(int testNumber, InputReader in, OutputWriter out) {
        String a = in.readString();
        String b = in.readString();
        if (solve(a, b))
            out.print("YES");
        else
            out.print("NO");
    }

    private boolean solve(String a, String b) {
        if (a.length() % 2 != 0)
            return a.equals(b);
        String s = smallest(a);
        String t = smallest(b);
        return s.equals(t);
    }
    private String smallest(String s) {
        if (s.length() % 2 == 1) return s;
        String s1 = smallest(s.substring(0, s.length()/2));
        String s2 = smallest(s.substring(s.length()/2, s.length()));
        if (s1.compareTo(s2) < 0) return s1 + s2;
        else return s2 + s1;
    }