LeetCode 242. Valid Anagram （验证变位词）

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.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

题目标签：Hash Table

　　题目给了我们两个string，让我们判断它们是不是变位词。

　　方法1：可以利用HashMap 来记录string s 的字母，和数量，接着用t 的字母和数量来验证。

　　方法2：可以把两个string 变为 char array，接着sort 两个array，比较它们是不是一致。

Java Solution 1:

Runtime beats 18.65%

完成日期：05/27/2017

关键词：HashMap

关键点：利用HashMap来存入s，用t 来验证

 class Solution

 {

     public boolean isAnagram(String s, String t)

     {

         /* Solution 1: HashMap */

         HashMap<Character, Integer> map = new HashMap<>();

         // first time: store each s char and occurrence into map

         for(int i=0; i<s.length(); i++)

         {

             char sChar = s.charAt(i);

             map.put(sChar, map.getOrDefault(sChar, 0) + 1);

         }

         // second time: compare t char with map to see match or not

         for(int i=0; i<t.length(); i++)

         {

             char tChar = t.charAt(i);

             if(!map.containsKey(tChar))

                 return false;

             if(map.get(tChar) == 1)

                 map.remove(tChar);

             else

                 map.put(tChar, map.get(tChar) - 1);

         }

         return map.size() == 0 ? true : false;

     }

 }

Java Solution 2:

Runtime beats 28.32%

完成日期：05/27/2017

关键词：Sort

关键点：把s 和t 都转化为char array，然后sort

 class Solution

 {

     public boolean isAnagram(String s, String t)

     {

         /* Solution 2: sort */

         if(s.length() != t.length() || s == null || t == null)

             return false;

         char[] s_arr = s.toCharArray();

         Arrays.sort(s_arr);

         char[] t_arr = t.toCharArray();

         Arrays.sort(t_arr);

         for(int i=0; i<s.length(); i++)

         {

             if(s_arr[i] != t_arr[i])

                 return false;

         }

         return true;

     }

 }

参考资料：N/A

LeetCode 题目列表 - LeetCode Questions List

巴特西

LeetCode 242. Valid Anagram （验证变位词）

最新文章

热门文章