LeetCode(34) -- 784, 788,

P784. Letter Case Permutation (Easy)

给一个字符串，我们可以把其中的字母换成任意大小写。列出所有的可能性。

答案

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<StringBuilder> ans = new ArrayList();
        ans.add(new StringBuilder());

        for (char c: S.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.add(new StringBuilder(ans.get(i)));
                    ans.get(i).append(Character.toLowerCase(c));
                    ans.get(n+i).append(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; ++i)
                    ans.get(i).append(c);
            }
        }

        List<String> finalans = new ArrayList();
        for (StringBuilder sb: ans)
            finalans.add(sb.toString());
        return finalans;
    }
}

21%

最优解

class Solution {
    public List<String> letterCasePermutation(String S) {
       List<String> answer = new ArrayList<String>();
        permutationHelper(answer, S.toCharArray() , 0);
        return answer;

    }

    public void permutationHelper(List<String> ans, char[] s , int index ){
        if( index == s.length){
            ans.add( new String(s));
            return;
        }
        if( Character.isAlphabetic(s[index])){
            s[index] = Character.toUpperCase(s[index]);
            permutationHelper(ans, s, index+1);
            s[index] = Character.toLowerCase(s[index]);
        }
        permutationHelper(ans, s , index+1);
    }
}

这个方法是最好的。

P788. Rotated Digits (Easy)

每个数字都旋转180度，如果能得到一个跟原来不一样的合法的数字，则该数有效。问从1到n一共有多少个这样的数字。

我的思路

每个数字都判断一下是否等于3，4，7或者2，5，6，9从而确定是否有效以及是否跟原来的数不一样了。

我的代码

public class E_788_RotatedDigits {
    public int rotatedDigits(int N) {
        int count = 0;
        for (int i = 1; i < N + 1; i++) {
            boolean valid = true;
            boolean different = false;
            int temp = i;
            while (temp != 0) {
                int r = temp % 10;
                if (r == 3 || r == 4 || r == 7) {
                    valid = false;
                    break;
                }
                if (r == 2 || r == 5 || r == 6 || r == 9) {
                    different = true;
                }
                temp /= 10;
            }
            if (valid && different) {
                count++;
            }
        }
        return count;
    }
}

48%

最优解

class Solution {
    public int rotatedDigits(int N) {
        char[] A = String.valueOf(N).toCharArray();
        int K = A.length;

        int[][][] memo = new int[K+1][2][2];
        memo[K][0][1] = memo[K][1][1] = 1;
        for (int i = K - 1; i >= 0; --i) {
            for (int eqf = 0; eqf <= 1; ++eqf)
                for (int invf = 0; invf <= 1; ++invf) {
                    int ans = 0;
                    for (char d = '0'; d <= (eqf == 1 ? A[i] : '9'); ++d) {
                        if (d == '3' || d == '4' || d == '7') continue;
                        boolean invo = (d == '2' || d == '5' || d == '6' || d == '9');
                        ans += memo[i+1][d == A[i] ? eqf : 0][invo ? 1 : invf];
                    }
                    memo[i][eqf][invf] = ans;
                }
        }

        return memo[0][1][0];
    }
}

肯定是为了保存算过的数据，可是弄K+1个2*2的矩阵，到底是怎么存数据的，实在是看不明白了。

P796. Rotate String (Easy)

把一个字符串最左边的字符挪到最右边，叫一次shift。如果字符串A经过若干次shift之后可以变成B，则返回true。

我的思路

一开始只想到暴力求解，可以用首字母是否相等来提高一点点效率。看答案最简单的方法是：把A重复一次，如果包含B，则返回true.

我的代码

class Solution {
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A + A).contains(B);
    }
}

答案

class Solution {
    public boolean rotateString(String A, String B) {
        if (A.equals(B)) return true;

        int MOD = 1_000_000_007;
        int P = 113;
        int Pinv = BigInteger.valueOf(P).modInverse(BigInteger.valueOf(MOD)).intValue();

        long hb = 0, power = 1;
        for (char x: B.toCharArray()) {
            hb = (hb + power * x) % MOD;
            power = power * P % MOD;
        }

        long ha = 0; power = 1;
        char[] ca = A.toCharArray();
        for (char x: ca) {
            ha = (ha + power * x) % MOD;
            power = power * P % MOD;
        }

        for (int i = 0; i < ca.length; ++i) {
            char x = ca[i];
            ha += power * x - x;
            ha %= MOD;
            ha *= Pinv;
            ha %= MOD;
            if (ha == hb && (A.substring(i+1) + A.substring(0, i+1)).equals(B))
                return true;

        }
        return false;
    }
}