C#LeetCode刷题之#383-赎金信(Ransom Note)

C#LeetCode刷题之#383-赎金信(Ransom Note)

问题

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。)

注意:你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false

canConstruct(“aa”, “ab”) -> false

canConstruct(“aa”, “aab”) -> true

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:You may assume that both strings contain only lowercase letters.

canConstruct(“a”, “b”) -> false

canConstruct(“aa”, “ab”) -> false

canConstruct(“aa”, “aab”) -> true

示例

public class Program {

    public static void Main(string[] args) {
        var ransomNote = "aa";
        var magazine = "abdfa";

        var res = CanConstruct(ransomNote, magazine);
        Console.WriteLine(res);

        ransomNote = "aa";
        magazine = "bb";

        res = CanConstruct2(ransomNote, magazine);
        Console.WriteLine(res);

        ransomNote = "bjaajgea";
        magazine = "affhiiicabhbdchbidghccijjbfj";

        res = CanConstruct3(ransomNote, magazine);
        Console.WriteLine(res);

        ransomNote = "edhi";
        magazine = "fhjeddgggbajhidhjchiedhdibgeaecffbbbefiabjdhggihccec";

        res = CanConstruct4(ransomNote, magazine);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool CanConstruct(string ransomNote, string magazine) {
        //LeetCode超出内存限制未AC
        var startIndex = -1;
        for(var i = 0; i < ransomNote.Length; i++) {
            if(magazine.Contains(ransomNote[i])) {
                startIndex = magazine.IndexOf(ransomNote[i]);
                magazine = magazine.Remove(startIndex, 1);
            } else {
                return false;
            }
        }
        return true;
    }

    private static bool CanConstruct2(string ransomNote, string magazine) {
        //这个解法没AC,输入 aa bb 在VS下返回false
        //但在LeetCode上显示返回 true
        //不知道为什么,有看官知道告诉我一下,多谢
        //总之这个解可能有问题,各位看官请注意!!!
        var i = 0;
        var j = 0;
        if(ransomNote.Length == 1 && !magazine.Contains(ransomNote))
            return false;
        while(i < ransomNote.Length) {
            var temp = ransomNote[i];
            while(j < magazine.Length) {
                if(magazine[j] != temp) j++;
                else {
                    i++;
                    break;
                }
            }
            if(i == ransomNote.Length - 1) return true;
            if(j >= magazine.Length) return false;
            j++;
        }
        return true;
    }

    private static bool CanConstruct3(string ransomNote, string magazine) {
        //哈希法
        var dic = new Dictionary<char, int>();
        foreach(var c in ransomNote) {
            if(dic.ContainsKey(c)) {
                dic[c]++;
            } else {
                dic[c] = 1;
            }
        }
        foreach(var c in magazine) {
            if(dic.ContainsKey(c)) {
                dic[c]--;
                if(dic[c] < 0) return false;
                if(dic[c] == 0) {
                    dic.Remove(c);
                }
            }
        }
        return dic.Count == 0;
    }

    private static bool CanConstruct4(string ransomNote, string magazine) {
        //用整型数组来统计26个字母
        //位置 0 代表字母 a,以此类推
        var statistics = new int[26];
        foreach(var c in magazine) {
            statistics[c - 'a']++;
        }
        foreach(var c in ransomNote) {
            if(--statistics[c - 'a'] < 0) return false;
        }
        return true;
    }

}

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

True
False
False
True

分析:

显而易见,以上4种算法的时间复杂度均为: O(n)

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

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

发表评论

登录后才能评论