459. Repeated Substring Pattern

Y3G 發布于2019-08-16 10:29 / 1648人閱讀

摘要：題目鏈接利用求數組的方法來做，利用自身的重復性，表示在中，最大的使得參考視頻所以如果這個是呈現的樣子的話，假設的大小是，則并且根據可知，一旦中間出現不滿足的情況，，所以必然不是的，如果結尾處少了的話，例如，雖然，但

459. Repeated Substring Pattern

題目鏈接：https://leetcode.com/problems...

利用kmp求prefix數組的方法來做，利用string自身的重復性，prefix[i] = k, k < i表示在s[0, i+1]中，最大的k使得s[0, k] == s[i-k+1, i+1]
參考視頻：
https://www.youtube.com/watch...

所以如果這個string是呈現repeated substring pattern的樣子的話，假設repeat的大小是m，則prefix[0] = prefix[1] = ... = prefix[m-1] = 0 并且prefix[n-1] = prefix[n-2] + 1 =... = prefix[m] + n-m-1 = n - m
根據n % m == 0可知：n%(n - prefix[n-1]) == 0，一旦中間出現不滿足pattern的情況，prefix[n-1] < n / 2，所以n-prefix[n-1] > n / 2必然不是n的divisor，如果結尾處少了的話，例如abcabca，雖然prefix[n-1] > n/2，但不滿足divisor的條件。

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int[] prefix = build(str);
        int n = str.length();
        return prefix[n-1] != 0 && n % (n - prefix[n-1]) == 0;
    }
    
    private int[] build(String s) {
        int n = s.length();
        int[] res = new int[n];
        int i = 1, j = 0;
        while(i < n) {
            // match, add the length
            if(s.charAt(i) == s.charAt(j)) {
                res[i] = j + 1;
                i++; j++;
            }
            // not match, return to previous
            else {
                if(j == 0) i++;
                else j = res[j-1];
            }
        }
        return res;
    }
}

GPU云服務器云服務器 459美元 Repeated Pattern Substring

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69889.html

LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
算法設計 - 尋找一個字符串的重復子串LRS

摘要：后綴數組最典型的是尋找一個字符串的重復子串字符串大小比較字符串大小比較是指字典順序，也就是對于兩個字符串。注意，在語言中，后綴數組記錄的也就是數組中的元素是一個字符指針，指向的是一個子串的起始字符。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨問題描述：首先這是一個單字符串問題。子字符...

shleyZ 2019-08-14 12:09 評論0 收藏0
[LeetCode] 686. Repeated String Match

Problem Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1. For example, with A = abcd and B = cdabcdab. ...

ashe 2019-08-16 13:34 評論0 收藏0
395. Longest Substring with At Least K Repeating C

摘要：題目要求找出字符串中的最長子字符串，滿足該子字符串中任何字符出現的次數都大于。思路和代碼這是一個經典的分治法解決的問題，關鍵在于我們如何將這個問題分解為更小的子問題。題目要求 Find the length of the longest substring T of a given string (consists of lowercase letters only) such th...

vvpvvp 2019-08-16 15:09 評論0 收藏0