美文网首页
算法(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)互为变形词

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