|
This post is completed by 2 users
|
Add to List |
23. Find Whether Two Strings are Permutation of each other
Objective: Given Two Strings, check whether one string is a permutation of other
Input: Two Strings Output: True or false based on whether strings are permutations of others or not.
Example:
"sumit" and "tiums" are permutations of each other. "abcd" and bdea" are not permutations of each other.
Approach:
Method 1: Time Complexity - O(nlgn)
Sort both the strings and compare it.
import java.util.Arrays;
public class Main {
public static boolean isPermutation(String s1, String s2){
if(s1.length()!=s2.length()){
return false;
}
char [] x = s1.toCharArray();
char [] y = s2.toCharArray();
Arrays.sort(x);
Arrays.sort(y);
return Arrays.toString(x).equals(Arrays.toString(y));
}
public static void main(String args[]){
String s1 = "sumit";
String s2 = "mtisu";
System.out.println(s1 +" and "+ s2 + " are permutation of each other? " + isPermutation(s1, s2));
s1 = "xyzab";
s2 = "bayzxx";
System.out.println(s1 +" and "+ s2 + " are permutation of each other? " + isPermutation(s1, s2));
}
}
def is_permutation(s1, s2):
if len(s1) != len(s2):
return False
x = sorted(s1)
y = sorted(s2)
return x == y
if __name__ == "__main__":
s1 = "sumit"
s2 = "mtisu"
print(f"{s1} and {s2} are permutations of each other? {is_permutation(s1, s2)}")
s1 = "xyzab"
s2 = "bayzxx"
print(f"{s1} and {s2} are permutations of each other? {is_permutation(s1, s2)}")
package main
import (
"fmt"
"sort"
)
func isPermutation(s1, s2 string) bool {
if len(s1) != len(s2) {
return false
}
x := sortString(s1)
y := sortString(s2)
return x == y
}
func sortString(s string) string {
r := []rune(s)
sort.Slice(r, func(i, j int) bool { return r[i] < r[j] })
return string(r)
}
func main() {
s1 := "sumit"
s2 := "mtisu"
fmt.Println(s1, "and", s2, "are permutations of each other?", isPermutation(s1, s2))
s1 = "xyzab"
s2 = "bayzxx"
fmt.Println(s1, "and", s2, "are permutations of each other?", isPermutation(s1, s2))
}sumit and mtisu are permutation of each other? true xyzab and bayzxx are permutation of each other? false
Method 2 : Using Hash Map- Time Complexity - O(n)
- Check if both Strings are having the same length, if not, return false.
- Create a Hash Map, make character as key and its count as value
- Navigate the string one taking each character at a time
- check if that character already exists in a hash map, if yes then increase its count by 1, and if it doesn't exist insert it into a hash map with the count as 1.
- Now navigate the second string taking each character at a time
- check if that character exists in the hash map, if yes then decrease its count by 1 and if it doesn't exist then return false.
- At the end navigate through the hash map and check if all the keys have 0 count against it if yes then return true else return false.
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class Main {
public static boolean isPermutation(String s1, String s2){
if(s1.length()!=s2.length()){
return false;
}
HashMap<Character, Integer> ht = new HashMap<>();
for(int i=0;i<s1.length();i++){
char c = s1.charAt(i);
if(ht.containsKey(c)){
int val = ht.get(c) + 1;
ht.put(c, val);
}else{
ht.put(c, 1);
}
}
for(int i=0;i<s2.length();i++){
char c = s2.charAt(i);
if(ht.containsKey(c)){
int val = (int)ht.get(c);
if(val==0){
return false;
}
val--;
ht.put(c, val);
}else{
return false;
}
}
Set keys = ht.keySet();
Iterator<Character> iterator = keys.iterator();
while(iterator.hasNext()){
char c = iterator.next();
if(ht.get(c)!=0){
return false;
}
}
return true;
}
public static void main(String args[]){
String s1 = "sumit";
String s2 = "mtisu";
System.out.println(s1 +" and "+ s2 + " are permutation of each other? " + isPermutation(s1, s2));
s1 = "xyzab";
s2 = "bayzxx";
System.out.println(s1 +" and "+ s2 + " are permutation of each other? " + isPermutation(s1, s2));
}
}
def is_permutation(s1, s2):
if len(s1) != len(s2):
return False
ht = {}
for c in s1:
if c in ht:
ht[c] += 1
else:
ht[c] = 1
for c in s2:
if c in ht:
if ht[c] == 0:
return False
ht[c] -= 1
else:
return False
for val in ht.values():
if val != 0:
return False
return True
if __name__ == "__main__":
s1 = "sumit"
s2 = "mtisu"
print(f"{s1} and {s2} are permutations of each other? {is_permutation(s1, s2)}")
s1 = "xyzab"
s2 = "bayzxx"
print(f"{s1} and {s2} are permutations of each other? {is_permutation(s1, s2)}")
package main
import "fmt"
func isPermutation(s1, s2 string) bool {
if len(s1) != len(s2) {
return false
}
ht := make(map[rune]int)
for _, c := range s1 {
if _, ok := ht[c]; ok {
ht[c]++
} else {
ht[c] = 1
}
}
for _, c := range s2 {
if val, ok := ht[c]; ok {
if val == 0 {
return false
}
ht[c]--
} else {
return false
}
}
for _, val := range ht {
if val != 0 {
return false
}
}
return true
}
func main() {
s1 := "sumit"
s2 := "mtisu"
fmt.Println(s1, "and", s2, "are permutations of each other?", isPermutation(s1, s2))
s1 = "xyzab"
s2 = "bayzxx"
fmt.Println(s1, "and", s2, "are permutations of each other?", isPermutation(s1, s2))
}sumit and mtisu are permutation of each other? true xyzab and bayzxx are permutation of each other? false