LeetCode備忘録_その3_Arrays & Hashing_Valid Anagram

概要

• LeetCodeを始めました。１テーマごとに解法と学びをメモします
• 今回テーマは「Arrays & Hashing_Valid Anagram」

テーマ詳細

原文

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false

日本語訳

※G翻訳
2 つの文字列 s と t を指定すると、t が s のアナグラムである場合は true を返し、そうでない場合は false を返します。 アナグラムは、通常は元の文字をすべて 1 回だけ使用して、別の単語またはフレーズの文字を再配置することによって形成された単語またはフレーズです。 例 1: 入力: s = "anagram"、t = "nagaram" 出力: true 例 2: 入力: s = "rat"、t = "car" 出力: false

解法

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        elif set(s) != set(t):
            return False
        else:
            for chr in set(s):
                if s.count(chr) != t.count(chr):
                    return False
                else:
                    pass
        return True

結果

• Runtime:21ms
• Beats 95.11% of users with Python 　※投稿日時点

思想

• アナグラムかどうかを判定できる条件として以下を始めに思いついた

  1. 文字数が同じ
  2. 含まれるアルファベットの種類が同じ

• 上記２つはfor文を用いなくても計算負荷少なく判定できるので、まず初めにこれらのフィルターを設けることにした

• 上記２つでは"aabb", "abbbのようなケースに対応できないことに気づく。これらが生じるケースは割合的に少なさそうなのでfor文を用いることにした
  3. 1単語目が含むアルファベットのユニークを取って、１文字ごとのcount数が2単語目と一致すること

学び

• 判定条件が複数ある場合は、処理が少ない条件から適用して判定できない場合は後続の判定条件に落としていくほうが効率が良い
• 上記の優先度は、基本的には処理量で良いと思うが、該当ケースが生じる確率も考慮に加えるとなお良い

感想

• 単語のユニークな文字を取ってくる方法は以前の投稿で学んだsetを使った方法で実施した
• LeetCodeで学んだ知識を早速使えて嬉しかった
• 実施時間が上位5%を取れて嬉しかった