Skip to content

Instantly share code, notes, and snippets.

@abatilo
Created January 18, 2017 03:06
Show Gist options
  • Save abatilo/18f0f943893b8274ed9a2c74f6c77144 to your computer and use it in GitHub Desktop.
Save abatilo/18f0f943893b8274ed9a2c74f6c77144 to your computer and use it in GitHub Desktop.
import java.util.*;
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int length = str.length();
if (length <= 1) return false;
List<Integer> factors = new ArrayList();
// Factor
for (int i = 1; i * 2 <= length; ++i) {
if (length % i == 0) {
factors.add(i);
factors.add(length / i);
}
}
Collections.sort(factors);
Collections.reverse(factors);
factors.remove(0);
HashSet<Integer> uniqueFactors = new HashSet<Integer>();
for (Integer n : factors) {
uniqueFactors.add(n);
}
for (Integer possibleLength : factors) {
String sub = str.substring(0, possibleLength);
boolean works = true;
for (int i = possibleLength; i <= str.length() - possibleLength; i += possibleLength) {
String sub2 = str.substring(i, i + possibleLength);
if (!str.substring(i, i + possibleLength).equals(sub)) {
works = false;
break;
}
}
if (works) { return works; }
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment