我最近在一個面試問題中被問到這個問題：給定一個輸入字符串，檢查它是否具有重復(fù)模式并返回真或假。例如： "abbaabbaabbaabba"是一個重復(fù)的模式"abba"private boolean checkPattern(String input) {
}我們?nèi)绾问褂谜齽t表達式和不使用正則表達式來解決它？我對使用正則表達式和不使用正則表達式的方法都感興趣。
4 回答
www說
TA貢獻1775條經(jīng)驗 獲得超8個贊
對于它的價值，我找到了一個使用正則表達式的解決方案。
訣竅是在非空的第一組上使用反向引用。
^(.+)(?:\1)+$
正如@PatrickParker 指出的那樣，如果您需要最小的重復(fù)模式，那么您可以使用惰性限定符
^(.+?)(?:\1)+$
繁華開滿天機
TA貢獻1816條經(jīng)驗 獲得超4個贊
如果沒有正則表達式，您將不得不遍歷每個可能的子字符串，該子字符串的長度可以被原始字符串的長度整除，從索引 0 開始，在原始字符串中并檢查它是否重復(fù)。要檢查它是否重復(fù)，您只需檢查pattern.length()字符串中的每個字符數(shù)，看看它是否是模式。例如，它看起來像這樣，
public boolean checkPattern(String str) {
String pattern = "";
for (int i = 0; i < str.length()/2; i++) {
pattern += str.charAt(i);
if (str.length() % pattern.length() == 0 && isRepeating(str, pattern)) {
return true;
}
}
return false;
}
public boolean isRepeating(String str, String pattern) {
String leftover = str;
int currIndex = leftover.indexOf(pattern);
while (currIndex == 0) {
if(currIndex + pattern.length() == leftover.length()) {
return true; // you have reached the last possible instance of the pattern at this point
}
leftover = leftover.substring(currIndex + pattern.length());
currIndex = leftover.indexOf(pattern);
}
return false;
}
就像用戶 thebjorn 提到的那樣，您可以通過僅在字符串的長度可被模式的長度整除時調(diào)用它來防止不必要的調(diào)用isRepeating，因此在 if 語句中進行模數(shù)檢查。此外，模式可以在字符串中重復(fù)的最大長度是str.length()/2.
躍然一笑
TA貢獻1826條經(jīng)驗 獲得超6個贊
我意識到這篇文章有點過時了，但它出現(xiàn)在關(guān)于這個主題的谷歌搜索的頂部，并且由于沒有一個答案提供我需要的東西，我最終制作了一個方法，我只是想添加它這篇文章供未來的搜索者使用。
此方法生成找到的一個或多個模式以及每個模式在原始字符串中重復(fù)的次數(shù)。
當(dāng)我使用 string.matches() 嘗試 @flakes 正則表達式時，只有當(dāng)模式并排時它才匹配 true。所以它會匹配 101101 但不匹配 101234101 （它似乎不知道模式 101 在那里兩次。
因此，如果您只需要知道您的字符串是否并排具有相同的模式，請使用以下代碼：
if (myString.matches("^(.+?)(?:\\1)+$")) {
//doSomethingHere
}
考慮到構(gòu)建一個模式子串的想法，我想出了這個方法，它基本上構(gòu)建了一個所有可能模式的列表。然后它遍歷該列表并檢查原始字符串以查看該模式是否在其中。顯然，它將忽略比較中的第一次命中，因為模式將始終在源字符串中命中一次……由于模式是從源字符串創(chuàng)建的。
這是代碼，顯然您可以根據(jù)需要對其進行按摩：
private void checkForPattern(String userString) {
String buildString;
LinkedList<String> patterns = new LinkedList<>();
int size = userString.length();
int hits;
int newSize;
String[] coreString = new String[size];
Map<String, Integer> hitCountMap = new HashMap<>();
for (int x = 0; x < size; x++) {
coreString[x] = userString.substring(x, x + 1);
}
for (int index = 0; index < size - 1; index++) {
buildString = coreString[index];
for (int x = index + 1; x < size; x++) {
buildString = buildString + coreString[x];
patterns.add(buildString);
}
}
for (String pattern : patterns) {
String check = userString.replaceFirst(pattern, "");
if (check.contains(pattern)) {
newSize = userString.replaceAll(pattern, "").length();
hits = (size - newSize) / pattern.length();
hitCountMap.put(pattern, hits);
}
}
for (String pattern : hitCountMap.keySet()) {
System.out.println("Pattern: " + pattern +
" repeated " + hitCountMap.get(pattern) +
" times.");
}
}
慕少森
TA貢獻2019條經(jīng)驗 獲得超9個贊
我不知道 RegEx，所以我會以不同的方式來做。這僅適用于字符串不是部分重復(fù)的字符串，即“xbcabbaabbaabbaxx”
首先，您獲取輸入字符串，并找到字符串大小的因素。素數(shù)意味著沒有重復(fù)模式，因為重復(fù)模式意味著模式字符串長度的至少 2 的倍數(shù)。
感謝 Tot Zam：尋找給定整數(shù)的因數(shù)
public ArrayList<Integer> findFactors(int num) {
ArrayList<Integer> factors = new ArrayList<Integer>();
// Skip two if the number is odd
int incrementer = num % 2 == 0 ? 1 : 2;
for (int i = 1; i <= Math.sqrt(num); i += incrementer) {
// If there is no remainder, then the number is a factor.
if (num % i == 0) {
factors.add(i);
// Skip duplicates
if (i != num / i) {
factors.add(num / i);
}
}
}
// Sort the list of factors
Collections.sort(factors);
return factors;
}
一旦你找到了數(shù)字的因子，在你的例子中是 16（結(jié)果是 1,2,4,8,16），并且不包括最大的因子（它本身），你現(xiàn)在可以創(chuàng)建一個循環(huán)并迭代細繩。您檢查每個值與之前的值，并檢查直到您使用 continue 獲得正確的值
例如，一個粗略的草圖：
boolean isRepeatingPattern = false;
for (Integer factor : factors) {
int iterations = stringSize / factor;
String previousSubstring = stringParam.substring(0, factor);
for (int i = 1; i < iterations; i++) {
int index = i * factor;
if (previousSubstring != stringParam.substring(index, index + factor)) break;
if (i == iterations - 1) repeatingPattern = true;
}
}
添加回答
舉報
0/150
提交
取消