同位字符串连接的最小长度

同位字符串连接的最小长度(medium)

做题过程

一开始想到了栈，但是如果内部有重复就不行。

算法概述

原题

本题要求为查找最短的同位字符串（即整个字符串均由该字符串组成）。

• 时间复杂度为$O(n \times T)
• 空间复杂度为：字符集

JAVA

class Solution {
    public int minAnagramLength(String s) {
        int n = s.length();
        // 直接枚举
        for (int i = 1; i < n; i++) {
            // 不能整除肯定不对
            if (n % i != 0) {
                continue;
            }
            if (check(s, i)) {
                return i;
            }
        }
        return n;
    }

    public boolean check(String s, int m) {
        // 字符集
        int[] count0 = new int[26];
        // 枚举所有子字符串是否相等
        for (int j = 0; j < s.length(); j += m) {
            int[] count1 = new int[26];
            // 记录当前字符串
            for (int k = j; k < j + m; k++) {
                count1[s.charAt(k) - 'a']++;
            }
            // 判断是否前一子字符串和当前字符串是否一样
            if (j > 0 && !Arrays.equals(count0, count1)) {
                return false;
            }
            count0 = count1;
        }
        return true;
    }
}

总结

难绷。