LeetCode466. Count The Repetitions

fan-jiaming 2020-04-26 原文

题目链接
- 传送门
题意
- 定义一个特殊的串, 现在给出串S1和S2的参数, 问: S2最多可以多少个连接起来扔是S1的子序列, 求出这个最大值
解题思路
- 注意s1与S1的区别, 可以去看题目描述, 预处理出s1从s2的每一个字符开始匹配, s1可以匹配到s2串尾的数量, 即如果从s2的当前下标开始匹配, 这一个s1最多可以匹配多少s2, 这个s1匹配完成后匹配到了s2的哪一个字符, 下一个s1匹配s2的话应该从哪一个下标开始, 因为串长最长100, 这个预处理时间消耗是很少的, 有了这个预处理的结果, 我们就可以O(n)的知道S1可以匹配多少个s2, 进而推算出匹配多少个S2.

AC代码

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int answer = 0;
    
        ArrayList<Integer> numArrayList = new ArrayList<Integer>();
        ArrayList<Integer> idxArrayList = new ArrayList<Integer>();
    
        for(int i = 0; i < s2.length(); ++i) {
    	int num = 0, idx = i;
    	for(int j = 0; j < s1.length(); ++j) {
    		if(s2.charAt(idx) == s1.charAt(j)) {
    			idx++;
    			if(idx == s2.length()) {
    				num++;
    				idx = 0;
    			}
    		}
    	}
    	numArrayList.add(num);
    	idxArrayList.add(idx);
        }
    
        int idx = 0;
    
        for(int i = 0; i < n1; ++i) {
            answer += numArrayList.get(idx);
            idx = idxArrayList.get(idx);
        }
    
        return answer / n2;
    }
}