变位词判断

题目

写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。http://www.lintcode.com/zh-cn/problem/two-strings-are-anagrams/

分析

通过变位词的定义,可以得出以下结论:

  • 两个字符串如果长度不相等,必然不是变位词

  • 对于互为变位词的两个字符串而言,他们包含的字符及其对应的数量相同

很容易联想到,通过map记录每个字符出现的次数,先扫描a字符串,得到a字符串中所有字符出现的次数;再扫描b字符串,减去对应字符出现的次数。如果两者互为变位词,那么map中所有的entry,其值都应该为0,否则必不互为变位词。

代码


public class Solution {
    
    
    protected void calculateCount(String s, Map< Character, Integer> map){
        for(int i = 0; i < s.length(); i++){
            Character c = Character.valueOf(s.charAt(i));
            
            if(map.containsKey(c)){
                map.put(c, map.get(c).intValue() + 1);
            }else{
                map.put(c, 1);
            }
        }
    }
    
    protected void compare(String t, Map< Character, Integer> map){
        for(int i = 0; i < t.length(); i++){
            Character c = Character.valueOf(t.charAt(i));
            
            if(map.containsKey(c)){
                map.put(c, map.get(c).intValue() - 1);
            }else{
                map.put(c, -1);
            }
        }
    }
    
    protected boolean isAllClear(Map< Character, Integer> map){
        for(Map.Entry< Character,Integer> item : map.entrySet()){
            if(item.getValue().intValue() != 0) return false;
        }
        return true;
    }
    
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        // write your code here
       Map< Character, Integer> map = new HashMap<>(); 
       calculateCount(s, map);
       compare(t, map);
       return isAllClear(map);
    }
};
Show Comments

Get the latest posts delivered right to your inbox.