C#LeetCode刷题之#686-重复叠加字符串匹配(Repeated String Match)

C#LeetCode刷题之#686-重复叠加字符串匹配(Repeated String Match)

问题

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。

举个例子,A = “abcd”,B = “cdabcdab”。

答案为 3, 因为 A 重复叠加三遍后为 “abcdabcdabcd”,此时 B 是其子串;A 重复叠加两遍后为”abcdabcd”,B 并不是其子串。

注意:A 与 B 字符串的长度在1和10000区间范围内。

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”.

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times (“abcdabcd”).

Note:The length of A and B will be between 1 and 10000.

示例

public class Program {

    public static void Main(string[] args) {
        var A = "abcd";
        var B = "cdabcdab";

        var res = RepeatedStringMatch(A, B);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int RepeatedStringMatch(string A, string B) {
        var length = Math.Ceiling(B.Length / (double)A.Length) + 1;
        var repeat = new StringBuilder();
        for(var i = 0; i < length; i++) {
            repeat.Append(A);
            if(repeat.Length < B.Length) continue;
            if(repeat.ToString().Contains(B)) return i + 1;
        }
        return -1;
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

3

分析:

设字符串A的长度是 m,字符串B的长度是 n,由于部分运行库的使用,以上算法的时间复杂度应当为: O(m*n) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3963

发表评论

登录后才能评论