466.统计重复个数

链接：466.统计重复个数
难度：Hard
标签：字符串、动态规划
简介：由 n 个连接的字符串 s 组成字符串 S，记作  S = [s,n]。例如，["abc",3]=“abcabcabc”。如果我们可以从 s2  中删除某些字符使其变为 s1，则称字符串 s1  可以从字符串 s2 获得。例如，根据定义，"abc" 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。现在给你两个非空字符串 s1  和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106  和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。请你找出一个可以满足使[S2,M] 从 S1  获得的最大整数 M 。

题解 1 - javascript

• 编辑时间：2020-04-20
• 执行用时：4132ms
• 内存消耗：34.7MB
• 编程语言：javascript
• 解法介绍：循环判断字符串长度，如果匹配 index+1。

/**
 * @param {string} s1
 * @param {number} n1
 * @param {string} s2
 * @param {number} n2
 * @return {number}
 */
var getMaxRepetitions = function (s1, n1, s2, n2) {
  const len1 = s1.length;
  const len2 = s2.length;
  let index2 = 0,
    count = 0;
  for (let i = 0; i < n1; i++) {
    for (let j = 0; j < len1; j++) {
      if (s1[j] === s2[index2]) index2++;
      if (index2 === len2) {
        index2 = 0;
        count++;
      }
    }
  }
  return parseInt(count / n2);
};

题解 2 - rust

• 编辑时间：2024-01-02
• 执行用时：260ms
• 内存消耗：10.65MB
• 编程语言：rust
• 解法介绍：同上。

fn str_to_vec(s: &String) -> Vec<char> {
    s.chars().collect()
}
impl Solution {
    pub fn get_max_repetitions(s1: String, n1: i32, s2: String, n2: i32) -> i32 {
        let (n1, n2) = (n1 as usize, n2 as usize);
        let s1 = str_to_vec(&s1);
        let s2 = str_to_vec(&s2);
        let (len1, len2) = (s1.len(), s2.len());
        let (mut k, mut idx, mut cnt) = (0, 0, 0);
        let mut arr = vec![0];
        while k < n1 {
            for i in 0..len1 {
                if s2[idx] == s1[i] {
                    idx = (idx + 1) % len2;
                    if idx == 0 {
                        cnt += 1;
                    }
                }
            }
            k += 1;
            arr.push(cnt);
            if idx == 0 {
                break;
            }
        }
        ((cnt * (n1 / k) + arr[n1 % k]) / n2) as i32
    }
}