leetcode面试准备:Valid Anagram

1 题目

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,

s = "anagram", t = "nagaram", return true.

s = "rat", t = "car", return false.

Note:

You may assume the string contains only lowercase alphabets.

接口: public boolean isAnagram(String s, String t)

2 思路

题意

对比两个字符串是否是一样的。

解

HashMap思想存储字符，字符串s往map里面存储，字符串t往map里面取。最后看map是否为空：if 空，true.

复杂度: Time: O(n) , Space:O(26)

3 代码

    public boolean isAnagram(String s, String t) {

        Map<Character, Integer> smap = new HashMap<Character, Integer>();

        int slen = s.length();

        int tlen = t.length();

        if (slen != tlen)

        	return false;

        for (int i = 0; i < slen; i++) {

        	Character c = s.charAt(i);

        	if (smap.containsKey(c)) {

        		int count = smap.get(c);

        		count++;

        		smap.put(c, count);

        	} else {

        		smap.put(c,1);

        	}

        }

        for (int i = 0; i < tlen; i++) {

        	Character c = t.charAt(i);

        	if (smap.containsKey(c)) {

        		int count = smap.get(c);

        		count--;

        		if(count == 0) {

        			smap.remove(c);

        		} else {

        			smap.put(c, count);

        		}

        	} else {

        		return false;

        	}

        }

        return smap.isEmpty();

    }

4 总结

HashMap思想。