首页 > 代码库 > Leetcode: Count The Repetitions
Leetcode: Count The Repetitions
Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc". On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”. You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1. Example: Input: s1="acb", n1=4 s2="ab", n2=2 Return: 2
目前只想出了Brute Force做法(1165ms), 看到有<20ms的做法,未深究:
1 public class Solution { 2 public int getMaxRepetitions(String s1, int n1, String s2, int n2) { 3 char[] arr1 = s1.toCharArray(); 4 char[] arr2 = s2.toCharArray(); 5 int i1 = 0, i2 = 0; // current position 6 int count1 = 0, count2 = 0; //# of times pass through s1/s2‘s end 7 8 while (count1 < n1) { 9 if (arr1[i1] == arr2[i2]) { 10 i2++; 11 if (i2 == arr2.length) { 12 i2 = 0; 13 count2++; 14 } 15 } 16 i1++; 17 if (i1 == arr1.length) { 18 i1 = 0; 19 count1++; 20 } 21 } 22 return count2/n2; 23 } 24 }
Leetcode: Count The Repetitions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。