美文网首页
算法(11)互为变形词

算法(11)互为变形词

作者: 来搞事情 | 来源:发表于2018-09-18 01:03 被阅读0次

描述
对于两个字符串A和B,如果A和B中出现的字符种类相同且每种字符出现的次数相同,则A和B互为变形词,请设计一个高效算法,检查两给定串是否互为变形词。

给定两个字符串A和B及他们的长度,请返回一个bool值,代表他们是否互为变形词。

测试样例:
"abc",3,"bca",3
返回:true

解法
使用一个HashMap记录字符出现的次数
第一遍遍历A,将字符出现的次数记录到map中
第二次遍历B,将map中的次数减去,如果有map中不存在的字符,或者map中记录的次数小于B中的次数,返回false

public boolean chkTransform(String A, int lena, String B, int lenb) {
        if (lena != lenb)
            return false;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < A.length(); i++) {
            if (map.containsKey(A.charAt(i))) {
                map.put(A.charAt(i), map.get(A.charAt(i)) + 1);
            } else {
                map.put(A.charAt(i), 1);
            }
        }

        for (int i = 0; i < B.length(); i++) {
            if (!map.containsKey(B.charAt(i)) || map.get(B.charAt(i)) <= 0) {
                return false;
            } else {
                map.put(B.charAt(i), map.get(B.charAt(i)) - 1);
            }
        }
        return true;
    }

相关文章

  • 算法(11)互为变形词

    描述对于两个字符串A和B,如果A和B中出现的字符种类相同且每种字符出现的次数相同,则A和B互为变形词,请设计一个高...

  • Cracking the Interview - Strings

    Making Anagram Alice最近开始研究密码学,她发现变形词非常有用。两个字符串互为变形词,如果它们具...

  • String

    判断两个字符串是否互为变形词 time = n(字符串长度), space = M(字符种类数)如果字符种类很多,...

  • 3_3变形词

    对于两个字符串A和B,如果A和B中出现的字符种类相同且每种字符出现的次数相同,则A和B互为变形词,请设计一个高效算...

  • 121. Best Time to Buy and Sell S

    最大子段和问题的变形:此题相关的算法是:Kadane算法代码:

  • 判断两个字符串是否互为变形词

    题目 给定两个字符串str1和str2,如果str1和str2中出现的字符种类一样且每种字符出现的次数也一样,那么...

  • Part 3: Cumulative weights and w

    在part2中,我们学习了unweighted random walk选择算法。本章节,我们将学习更高级的变形算法...

  • 每日两道算法题 - 字母异味词判断

    问题 给定两个字符串,判断两个字符串是否互为异味词异味词: 两个字符串中字符出现的次数相同,则互为异味词 思路 1...

  • 变形(11)

    每次和海霞海阔天空胡吹海侃之后,就会觉得心境又开阔了一些。作为成年人生活以后,年龄极速占了上风,渐渐地对谁都有了保...

  • 字符串类型面试题目总结

    字符串系列题目一览: 1.t1是否有与t2树拓扑结构相同的子树2.判断两个字符串是否互为变形词?3.判断两个字符串...

网友评论

      本文标题:算法(11)互为变形词

      本文链接:https://www.haomeiwen.com/subject/swfsnftx.html