https://leetcode.com/problems/count-the-repetitions/

下面是我的方法，结果对的，超时了。。。

package com.company;class Solution {    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {        int len1 = s1.length();        int[][]stores = new int[26][len1];        int[] pos = new int[26];        int[] cur = new int[26];        int index;        for (int i=0; i
     
      = pos[index] * n1) {                        return ret;                    }                    int newPos = 0;                    do {                        newPos = cur[index] / pos[index] * len1 + stores[index][cur[index] % pos[index]];                        cur[index] = cur[index] + 1;                    } while (newPos < curPos && cur[index] < pos[index] * n1);                    if (newPos < curPos) {                        return ret;                    }                    curPos = newPos + 1;                }            }            ret++;        }    }}public class Main {    public static void main(String[] args) throws InterruptedException {        String s1 = "niconiconi";        int n1 = 99981;        String s2 = "nico";        int n2 = 81;        Solution solution = new Solution();        int ret  = solution.getMaxRepetitions(s1, n1, s2, n2);        // Your Codec object will be instantiated and called as such:        System.out.printf("ret:%d\n", ret);        System.out.println();    }}
     

 

优化之后的结果，还是超时：

加了string到array的优化，另外每次循环之后坐个判断剪枝。

 

package com.company;class Solution {    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {        int len1 = s1.length();        int[][]stores = new int[26][len1];        int[] pos = new int[26];        int[] cur = new int[26];        int index;        for (int i=0; i
     
      = curPos) {                            break;                        }                    }                    if (newPos < curPos) {                        /*System.out.printf("index %d cur[index] %d pos[index] %d cur/-pos %d, store %d\n",                                index, cur[index], pos[index], cur[index] % pos[index], stores[index][cur[index] % pos[index]]);                        System.out.printf("newPos %d curPos %d\n",                                newPos, curPos);                                */                        return ret;                    }                    curPos = newPos + 1;                }            }            ret++;            for (int i=0; i<26; i++) {                if (pos[i] > 0 && cur[i] >= pos[i] * n1) {                    return ret;                }            }        }    }}public class Main {    public static void main(String[] args) throws InterruptedException {        String s1 = "acb";        int n1 = 4;        String s2 = "ab";        int n2 = 2;        Solution solution = new Solution();        int ret  = solution.getMaxRepetitions(s1, n1, s2, n2);        // Your Codec object will be instantiated and called as such:        System.out.printf("ret:%d\n", ret);        System.out.println();    }}
     

 

用了这种Brute Force的方法，居然比我的快。。。。。。

public class Solution {    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {        char[] array1 = s1.toCharArray(), array2 = s2.toCharArray();        int count1 = 0, count2 = 0, i = 0, j = 0;                while (count1 < n1) {            if (array1[i] == array2[j]) {                j++;                if (j == array2.length) {                    j = 0;                    count2++;                }            }            i++;            if (i == array1.length) {                i = 0;                count1++;            }        }                return count2 / n2;    }}

 

（完）