【LeetCode】Valid Anagram解題報告

Valid Anagram
[LeetCode]
https://leetcode.com/problems/valid-anagram/
Total Accepted: 78186 Total Submissions: 187211 Difficulty: Easy
Question
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.
Ways
この問題が最初に私が考えたのは、s文字列の各文字がtで見つかるかどうかの方法です.これは明らかに間違っている.何度も起こった問題を考慮しなかった.すなわち、2つの文字列の長さが等しく、各文字の出現回数が同じであれば、変位語である.
タイトルには小文字しかないと言っていますが、それは26文字しかありません.出現頻度を集計すればいいです.2つの文字列に現れる語の頻度が同じであれば、変位語であることを示します.
アルゴリズムは次のとおりです.

public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
       int[] sTimes=new int[26];
       int[] tTimes=new int[26];
       for(int i=0;i<s.length();i++){
           sTimes[s.charAt(i)-'a']+=1;
           tTimes[t.charAt(i)-'a']+=1;
       }
       for(int i=0;i<sTimes.length;i++){
           if(sTimes[i]!=tTimes[i]){
               return false;
           }
       }
       return true;
    }
}

AC:12ms
2つの配列を用いて保存されているのが見えます.このように空間の複雑さが大きく、1つで保存できます.
sの場合、これを文字配列として遍歴し、遍歴中に出現する文字のカウントごとに1を加算します.
tについても同様に遍歴し,出現する文字ごとにカウントを1つ減らす.
sとtがanagramの場合、最後のcharcount配列のすべての文字のカウントは0でなければなりません.そうしないとanagramではありません.
簡略化されたコード:

public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
       int[] times=new int[26];
       for(int i=0;i<s.length();i++){
           times[s.charAt(i)-'a']+=1;
           times[t.charAt(i)-'a']-=1;
       }
       for(int i=0;i<times.length;i++){
           if(times[i]!=0){
               return false;
           }
       }
       return true;
    }
}

AC:10ms
また、s文字列を遍歴して、tに出てくる同じ文字を「あ、終わった後の結果を見て」に置き換えることができるという考え方も提供されています.コードを書いた結果、タイムアウトになります.時間の複雑さはあまり高くないと感じますが、indexOf()メソッド自体が計算より時間がかかる可能性があります.
これは,文字列問題ができるだけ文字配列に変換され,効率が高いことを示している.文字列自体の方法で操作するとタイムアウトする可能性があります.

public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
       for(int i=0;i<s.length();i++){
           if(t.indexOf(s.charAt(i))==-1){
               return false;
           }else{
               t.replace(""+s.charAt(i),"");
           }
       }
       if(!t.equals("")){
           return false;
       }
       return true;
    }
}

Date
2016/4/30 13:08:21