Using Hash Set to Determine if a String is the Permutation of An
- Time:2020-09-09 13:08:38
- Class:Weblog
- Read:36
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) —
Recommend:7 Ways To Deal With AdBlock Users If You’re A Blogger
2020 Design Trends [Infographic]
8 Content Marketing Plugins You Need For Your WordPress Blog
Tips to Make Money from the Comfort of Your Own Home
5 Tips for Protecting Your Freelance Business from Liabilities
5 Easy Ways On How To Build An Authority Website
How to Protect Your WordPress Site From Hackers
Top 10 Relationship Blogs With the Best Pieces of Advice in 2020
How to Construct Binary Search Tree from Preorder Traversal in P
Dynamic Programming Algorithm to Compute the Block Sum in a Matr
- Comment list
-
- Comment add