Using Hash Set to Determine if a String is the Permutation of An

  • 时间:2020-09-09 13:08:38
  • 分类:网络文摘
  • 阅读:93 次

Given two strings s1 and s2, write an algorithm to determine if s1 is one permutation of s2.

For example:
s1 = “abc”, s2 = “bca”
output: true

s1 = “abc”, s2 = “bad”
output: false

Algorithm to Determine if a String is the Permutation of Another String

The fastest way to determine this is to use hash sets. If both strings (s1 and s2) are of different sizes, the result has to be false. Otherwise, we can convert both into two hash sets and simply compare the equality of both hash sets.

In C++, you can directly compare the the equality of both hash sets, either set (based on Red-Black Tree) or unordered_set (based on Hash Map):

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        unordered_set<char> a(begin(s1), end(s1));
        unordered_set<char> b(begin(s2), end(s2));
        return a == b;
    }
};
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        unordered_set<char> a(begin(s1), end(s1));
        unordered_set<char> b(begin(s2), end(s2));
        return a == b;
    }
};

Using unordered_set in C++, you will have a O(N) complexity however if you are using set (which keeps the keys in order by tree), the complexity is O(N.Log(N)).

In Python, we can do the same, with less code:

1
2
3
4
5
class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        return set(s1) == set(s2)
class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        return set(s1) == set(s2)

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
开了芙蓉,醉了石榴  最美的永远是母亲  捶背作文150字  蹇叔哭师原文及翻译  百家讲坛系列节目《易中天品三国》MP3蓝奏云下载  百家讲坛系列节目《国史通鉴(第一部)》蓝奏云mp3下载  展喜犒师原文及翻译  介之推不言禄原文及翻译  寺人披见文公原文及翻译  子鱼论战原文及翻译 
评论列表
添加评论