乐趣区

关于java:LeetCode459重复的子字符串

反复的子字符串

题目形容:给定一个非空的字符串,判断它是否能够由它的一个子串反复屡次形成。给定的字符串只含有小写英文字母,并且长度不超过 10000。

示例阐明请见 LeetCode 官网。

起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

解法一:字符串遍历

首先,判断非凡状况,当该字符串只有一个字符时,不可能由子串反复形成,所以间接返回 false;

否则,别离遍历子串的长度从 1~ 原字符串长度的一半,而后循环判断:

  • 如果以后子串的长度不能被原字符串的长度模除后果为 0,阐明这个子串不可能多次重复结构成原字符串,间接跳过;
  • 获取以后要判断的子串;
  • 依据原字符串的长度取得以后子串须要反复多少次能力形成原字符串;
  • 遍历判断是否能够反复形成原字符串,如果能够,间接返回 true,否则,持续判断下一个子串。

最初,如果没有子串能够反复屡次形成原字符串,则返回 false。

public class LeetCode_459 {public static boolean repeatedSubstringPattern(String s) {
        // 非凡状况,当该字符串只有一个字符时,不可能由子串反复形成,所以间接返回 false
        if (s.length() == 1) {return false;}
        // 记录原字符串的长度
        int len = s.length();
        // 别离遍历子串的长度从 1~ 原字符串长度的一半
        for (int i = 1; i <= len / 2; i++) {
            // 如果以后子串的长度不能被原字符串的长度模除后果为 0,阐明这个子串不可能多次重复结构成原字符串,间接跳过
            if (len % i != 0) {continue;}
            // 获取以后要判断的子串
            String repeatSubStr = s.substring(0, i);
            boolean allRepeat = true;
            // 以后子串须要反复多少次能力形成原字符串
            int count = len / i;
            // 遍历判断是否能够反复形成原字符串
            for (int j = 1; j < count; j++) {if (!s.substring(j * i, (j + 1) * i).equals(repeatSubStr)) {
                    allRepeat = false;
                    break;
                }
            }
            if (allRepeat) {return true;}
        }
        return false;
    }

    public static void main(String[] args) {
        // 测试用例,冀望输入:true
        System.out.println(repeatedSubstringPattern("abab"));
    }
}

【每日寄语】 挫折是一块石头,对于弱者来说它是拌脚石,让你停步不前。而对于强人来说它是垫脚石,使你站得更高。

退出移动版