Linkedin Interview Question
Software Engineer / DevelopersTeam: Application
Country: United States
Interview Type: Phone Interview
Urik beat me to it.
Working python code:
def string_color_distribution(s):
max_color_so_far = -1
color_mapping = {}
color_distribution = []
for c in s:
if c in color_mapping:
curr_color = color_mapping[c]
else:
curr_color = max_color_so_far + 1
max_color_so_far += 1
color_mapping[c] = curr_color
color_distribution.append(curr_color)
return color_distribution
def are_isomorphs(s1, s2):
if len(s1) != len(s2) or len(set(a)) != len(set(b)):
return False
s1_cd = string_color_distribution(s1)
s2_cd = string_color_distribution(s2)
for i, color in enumerate(s1_cd):
if color != s2_cd[i]:
return False
return True
a = raw_input()
b = raw_input()
print are_isomorphs(a,b)
@Urik Very smart solution. Here is my implementation in python for your solution.
def IsIsoMorphic(a,b):
dictA = dictB = defaultdict(str)
for i,c in enumerate(a):
dictA[c] = i
dictB[b[i]] = i
return encode(b,dictB) == encode(a,dictA)
def encode(a,dic):
return ''.join(str(dic[c]) for c in a)
match the character occurence.
ofo or foo-- 1 & 2
app or ppa--1 & 2
so isomorphic
ofoxxxy--1,1,2,3
applllz--1,1,2,3
so isomorphic.
if there is single instances of each characters in both string then isomorphic.
Good sol but you can just keep Hash<char, char> for each string. If the mapping already exists and is different then the old one return false.
@nastra don't u notice that the ordering of the second should be the same as first word. in your case, ofo, app has different orderings. and I think if we can ignore ordering, this problem is too simple, it's just like a modification of permutation, where use different character to replace original.
my solution:
public static boolean check(String s,String t){
if(s.length()!=t.length()) return false;
HashMap<Character,Character> map1=new HashMap<Character, Character>();
HashMap<Character,Character> map2=new HashMap<Character, Character>();
for(int i=0;i<s.length();i++){
char c1=s.charAt(i);
char c2=t.charAt(i);
if(map1.containsKey(c1)){
if(map1.get(c1)!=c2) return false;
}
if(map2.containsKey(c2)){
if(map2.get(c2)!=c1) return false;
}
map1.put(c1, c2);
map2.put(c2, c1);
}
return true;
}
public static boolean checkIsmorphic(String s1, String s2){
int len = s1.length();
if(s2.length()!=len)
return false;
int[] firstS = new int[26];
int[] secondS = new int[26];
for(int i=0; i<len; i++){
int c1 = (int)s1.charAt(i)-96;
int c2 = (int)s2.charAt(i)-96;
int index1 = c1-1;
int index2 = c2-1;
if(firstS[index1]==0){
firstS[index1] = c2;
secondS[index2] = c1;
} else if(firstS[index1]!=c2||secondS[index2]!=c1){
return false;
}
}
return true;
}
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int flag=0;
string a="app1111p";
string b="21q3333q";
//cout<<a<<b;
if(a.length()!=b.length())
{
cout<<"sorry ASS"<<endl;
flag=1;
}
int hashmap[256]={0};
for(int i=0;i<a.length();i++)
{
if(hashmap[a[i]]==0)
{
hashmap[a[i]]=int(b[i]);
//cout<<a[i]<<hashmap[a[i]]<<endl;;
}else if((hashmap[a[i]])==int(b[i]))
{
//cout<<"good to go"<<endl;;
}else
if ((hashmap[a[i]])!=b[i])
{
//cout<<"sorry Ass"<<endl;
flag=1;
break;
}
}
if(!flag)
cout<<"true";
else
cout<<"false";
}
public static boolean isIsomorphic(String inputString1, String inputString2) {
int length1 = inputString1.length();
int length2 = inputString2.length();
if (length1 != length2) {
return false;
}
if (length1 == 1) {
return true;
}
Map<Character, Character> characterMap = new HashMap<Character, Character>();
for (int i = 0; i < length1; i++) {
if (!characterMap.containsKey(inputString1.charAt(i))) {
characterMap.put(inputString1.charAt(i), inputString2.charAt(i));
}
if (!characterMap.get(inputString1.charAt(i)).equals(inputString2.charAt(i))) {
return false;
}
}
return true;
}
public static boolean isIsomorphic(String inputString1, String inputString2) {
int length1 = inputString1.length();
int length2 = inputString2.length();
if (length1 != length2) {
return false;
}
if (length1 == 1) {
return true;
}
Map<Character, Character> characterMap = new HashMap<Character, Character>();
for (int i = 0; i < length1; i++) {
if (!characterMap.containsKey(inputString1.charAt(i)) && !characterMap.containsValue(inputString2.charAt(i))) {
characterMap.put(inputString1.charAt(i), inputString2.charAt(i));
}
if (characterMap.get(inputString1.charAt(i)) == null) {
return false;
}
if (!characterMap.get(inputString1.charAt(i)).equals(inputString2.charAt(i))) {
return false;
}
}
return true;
}
// fixed a bug
Your solution runs in O(n^2) because map.containsValue() searches the entire map every time.
just make the character in second string as the key, since key is unique, but value is not, thus you can make sure for that key, the value should always be same.
public static boolean check(String s,String t){
if(s.length()!=t.length()) return false;
HashMap<Character,Character> map = new HashMap<Character,Character>();
for(int i=0;i<s.length();i++){
char c1 = s.charAt(i);
char c2 = t.charAt(i);
if(!map.containsKey(c2))
map.put(c2, c1);
else{
if(map.get(c2)!=c1) return false;
}
}
return true;
}
package com.test;
import java.util.HashMap;
import java.util.Map;
public class Isomorphic {
public static boolean isIsomorphic1(String s1, String s2){
if(s1.length() != s2.length())
return false;
else if(s1.length()==1)
return true;
else
{
Map<Character,Integer> map1 = new HashMap<Character, Integer>();
StringBuffer encodingString1 = new StringBuffer();
Map<Character,Integer> map2 = new HashMap<Character, Integer>();
StringBuffer encodingString2 = new StringBuffer();
for(int i=0;i<s1.length();i++){
if(!map1.containsKey(s1.charAt(i))){
map1.put(s1.charAt(i), i);
}
encodingString1.append(map1.get(s1.charAt(i)));
if(!map2.containsKey(s2.charAt(i))){
map2.put(s2.charAt(i), i);
}
encodingString2.append(map2.get(s2.charAt(i)));
}
return encodingString1.toString().equals(encodingString2.toString());
}
}
public static void main(String[] args) {
String s1 = "ab";
String s2 = "ca";
System.out.println(isIsomorphic1(s1, s2));
}
}
public static boolean findIsomophric(String a, String b){
//length doesn't match
if (a.length() != b.length()){
return false;
}
HashMap<Character,Character> bucket = new HashMap<Character,Character>();
for (int i=0; i<a.length(); i++){
if (bucket.containsKey(a.charAt(i))){
if (b.charAt(i)!=bucket.get(a.charAt(i))){
return false;
}
}
else if (bucket.containsKey(b.charAt(i))){
if (a.charAt(i)!=bucket.get(b.charAt(i))){
return false;
}
}
else{
// add both ways
bucket.put(a.charAt(i), b.charAt(i));
bucket.put(b.charAt(i), a.charAt(i));
}
}
return true;
}
I created my own class and used a map-based approach.
I build maps for both strings and check if they are equivalent.
public class IsomorphicStrings {
private static class Mapping{
private final Character c;
private final List<Integer> integers;
public Mapping(Character c, List<Integer> integers) {
this.c = c;
this.integers = integers;
}
private Character getC() {
return c;
}
private List<Integer> getIntegers() {
return integers;
}
}
public static List<Mapping> getMap(String s) throws Exception {
if(s== null || s.isEmpty()) throw new Exception("String cannot be null or empty");
LinkedHashMap<Character, List<Integer>> map = new LinkedHashMap<Character, List<Integer>>();
char[] chars = s.toCharArray();
for(int i = 0; i < chars.length; i++){
if(!map.containsKey(chars[i])) map.put(chars[i], new ArrayList<Integer>());
map.get(chars[i]).add(i);
}
List<Mapping> result = new ArrayList<Mapping>();
for(Character c : map.keySet())
result.add(new Mapping(c, map.get(c)));
return result;
}
public static boolean areIsomorphic(String a, String b) throws Exception {
if(a.length() != b.length()) return false;
List<Mapping> mapA = getMap(a);
List<Mapping> mapB = getMap(b);
if(mapA.size() != mapB.size()) return false;
for(int i = 0; i< mapA.size(); i++){
Mapping fromA = mapA.get(i);
Mapping fromB = mapB.get(i);
if(fromA.getIntegers().size() != fromB.getIntegers().size()) return false;
for(int j = 0; j < fromA.getIntegers().size(); j++)
if(fromA.getIntegers().get(j) != fromB.getIntegers().get(j)) return false;
}
return true;
}
}
Can be easily solved using a map and a set. Map for maintaining the characters of string1 mapped to string2, and a set to track the characters of string2 which have been mapped before.
#include<iostream>
#include<map>
#include<string>
#include<set>
using namespace std;
bool areIsomorphic(string str1, string str2)
{
int len1 = str1.length();
int len2 = str2.length();
if(len1 != len2) return false;
map<char, char> charMap;
set<char> visitSet;
for (int i = 0; i < len1; i++)
{
map<char, char>:: iterator itCharMap = charMap.find(str1[i]);
set<char>::iterator itVisitSet = visitSet.find(str2[i]);
if(itCharMap == charMap.end()) // str1 char not found, i.e. it hasn't been initialized yet.
{
if(itVisitSet != visitSet.end()) // str2 char found, i.e., it has already been mapped.
return false;
charMap[str1[i]] = str2[i];
visitSet.insert(str2[i]);
}
else if (itCharMap->second != str2[i]) // str1 char not found,
return false;
}
return true;
}
int main()
{
string in1, in2;
cout << "\nEnter string1: ";
cin >> in1;
cout << "\nEnter string2: ";
cin >> in2;
areIsomorphic(in1, in2) ? cout << "\nTRUE" : cout << "\nFALSE";
int temp;
cin >> temp;
return 0;
}
public class IsomorphicString {
private String s1;
private String s2;
public IsomorphicString(String s1, String s2) {
this.s1 = s1;
this.s2 = s2;
}
public boolean isIsomorphic() {
int[] s1_arr = new int[256];
int[] s2_arr = new int[256];
if( s1.length() != s2.length() ) {
return false;
}
for( int i = 0; i < s1.length(); i++ ) {
s1_arr[s1.charAt(i)] = s1_arr[s1.charAt(i)] + 1;
s2_arr[s2.charAt(i)] = s2_arr[s2.charAt(i)] + 1;
}
Arrays.sort(s1_arr);
Arrays.sort(s2_arr);
for( int i = 0; i < s1_arr.length; i++ ) {
if( s1_arr[i] != s2_arr[i] ) {
return false;
}
}
return true;
}
public static void main(String[] args) {
IsomorphicString is = new IsomorphicString("Hello", "World");
System.out.println(is.isIsomorphic());
}
}
O(n lg n) depending on the sort used.
I used two hashmaps, one to keep track if we already changed the mapping of a letter once and the other to keep track of the mappings.
Runtime O(n), space O(n)
{{
public boolean isIsomorphic(String s1, String s2) {
if(s1.length() != s2.length()) return false;
HashMap <Character, Boolean> used = new HashMap<Character, Boolean>();
HashMap <Character, Character> map = new HashMap <Character, Character>();
for (int i = 0; i < s1.length(); i++) {
if(!map.containsKey(s1.charAt(i))) {
map.put(s1.charAt(i), s1.charAt(i));
used.put(s1.charAt(i), false);
}
}
for (int j = 0; j < s1.length();j++){
if(s1.charAt(j) != s2.charAt(j)) {
if(used.get(s1.charAt(j)) == true &&
map.get(s1.charAt(j)) != s2.charAt(j)) return false;
else {
map.put(s1.charAt(j), s2.charAt(j));
used.put(s1.charAt(j), true);
}
}
}
return true;
}
}}
public boolean isIsomorphic(String s1, String s2) {
if(s1.length() != s2.length()) return false;
HashMap <Character, Boolean> used = new HashMap<Character, Boolean>();
HashMap <Character, Character> map = new HashMap <Character, Character>();
for (int i = 0; i < s1.length(); i++) {
if(!map.containsKey(s1.charAt(i))) {
map.put(s1.charAt(i), s1.charAt(i));
used.put(s1.charAt(i), false);
}
}
for (int j = 0; j < s1.length();j++){
if(s1.charAt(j) != s2.charAt(j)) {
if(used.get(s1.charAt(j)) == true &&
map.get(s1.charAt(j)) != s2.charAt(j)) return false;
else {
map.put(s1.charAt(j), s2.charAt(j));
used.put(s1.charAt(j), true);
}
}
}
return true;
}
Use runtime encoding. It doesn't matter what the characters are, just that the occurrences of each are the same in the same position. Leveraging f#'s value equality of lists you can do an O(n) pass
let runtimeEncode (str:string) =
seq{
let c = ref str.[0]
let count = ref 0
for r in str do
if !c = r then
count := !count + 1
else
yield !count
count := 1
c := r
yield !count
} |> Seq.toList
let isomorph str1 str2 = (runtimeEncode str1) = (runtimeEncode str2)
You can also lazy evaluate the whole thing to shortcircuit if you encounter a set of letters that no longer map
let runtimeEncode (str:string) =
seq{
let c = ref str.[0]
let count = ref 0
for r in str do
if !c = r then
count := !count + 1
else
yield !count
count := 1
c := r
yield !count
}
let isomorph str1 str2 =
if String.length str1 <> String.length str2 then
false
else
Seq.zip (runtimeEncode str1) (runtimeEncode str2)
|> Seq.takeWhile (fun (a,b) -> a = b)
|> Seq.length
|> (=) (String.length str1)
Here is Simple Solution:
public static boolean isIsomorphic(String str1, String str2) {
int n1 = str1.length();
int n2 = str2.length();
if(n1 != n2) {
return false;
}
HashMap<Character, Character> map = new HashMap<Character, Character>();
for(int i = 0; i< n1; i++) {
char ch = str2.charAt(i);
if(map.containsKey(ch)) {
char c = map.get(ch);
if (c != str1.charAt(i)){
return false;
}
} else {
map.put(ch, str1.charAt(i));
}
}
return true;
}
#include <iostream>
#include <map>
using namespace std;
int main(){
map<char,char> m;
map<char,char> m1;
string s1;
string s2;
char dup1[100];
char dup2[100];
cin>>s1;
cin>>s2;
if(s1.length()!=s2.length())
cout<<"False"<<endl;
else{
char next='a';
for(int i=0;i<s1.length();i++){
if(m.find(s1[i])==m.end()){
m[s1[i]]=next;
dup1[i]=next;
next++;
}
else{
dup1[i]=m[s1[i]];
}
}
next='a';
for(int i=0;i<s2.length();i++){
if(m1.find(s2[i])==m1.end()){
m1[s2[i]]=next;
dup2[i]=next;
next++;
}
else{
dup2[i]=m1[s2[i]];
}
}
for(int i=0;i<s1.length();i++){
if(dup1[i]!=dup2[i]){
cout<<"False"<<endl;
return 0;
}
}
cout<<"True"<<endl;
}
}
public boolean isOmorphic(String str1, String str2){
if(str1.length() != str2.length()){
return false;
}
if(str1.length() == 0){
return true;
}
HashMap<Character, Character> map = new HashMap<Character, Character>();
for(int i=0; i<str1.length(); i++){
if(map.containsKey(str1.charAt(i))){
if(map.get(str1.charAt(i)) != str2.charAt(i)){
return false;
}
else{
continue;
}
}else{
map.put(str1.charAt(i), str2.charAt(i));
}
}
return true;
}
private static boolean isIsomorphic(String s1, String s2) {
// optimization check
if (s1.length() != s2.length()) {
return false;
}
Hashtable table = new Hashtable();
for (int i=0; i < s1.length(); i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (table.containsKey(c1)) {
if ((Character) table.get(c1) != c2) {
return false;
}
} else {
if (table.containsValue(c2)) {
return false;
}
table.put(c1, c2);
}
}
return true;
}
I don't know wheter I'am being stupid again. Can't the following code work?
bool isomorphic(const string& source, const string& target)
{
if(target.size() != source.size()) return false;
char mapped[128] = {0}; //no mapping has been done at first
for(string::size_type i = 0, s = target.size(); i < s; ++i){
if(mapped[source[i]]) return false;//the letter of same position in source has already been mapped
mapped[source[i]] = target[i]; //map source[i] to target[i]
}
return true;
}
public static boolean isomorphic(String s1, String s2){
if (s1.length() != s2.length()) return false;
if (s1.length() == 0) return true;
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
int[] code = new int[s1.length()];
for (int i=0; i<s1.length(); i++){
char c = s1.charAt(i);
if (!map.containsKey(c)){
map.put(c,i);
code[i] = i;
}
else
code[i] = map.get(c);
}
map.clear();
for (int i=0; i<s1.length(); i++){
char c = s2.charAt(i);
if (!map.containsKey(c)){
if (code[i]!=i) return false;
map.put(c,i);
}
else {
if (code[i] != map.get(c)) return false;
}
}
return true;
}
public static void search(int[] num, int target, int start, int end){
if(start>end){
System.out.println("No result.");
return;
}
int mid = (start + end) / 2;
if(num[mid]==target){
System.out.println(num[mid]);
return;
} else if(num[mid]<target)
search(num, target, mid+1, end);
else if(num[mid]>target)
search(num, target, start, mid-1);
}
This solution, unless i'm misinterpreting the problem also works. and runs in O(n) time using an addition data struct (a hashset)
boolean checkProperWordIsoporphicMapping(String aa, String bb){
if(aa.lenght() != bb.lenght()) return false //incorrect word mapping, not same size
Character[] c = ArrayUtils.toObject(aa.toCharArray());
Character[] b = ArrayUtils.toObject(bb.toCharArray());
Hashset<Character> hs = new Hashset<Character>();
for(int i =0, j=0; i < c.size(); i++, j++){
if(hs.get(b[j]) && (a[i] != b[j]) return false;//if the char was mapped before and the new mapping char is a different letter, we have a problem
hs.add(b[j]);//add to hashset
}
return true; //runs in O(n)
}
#include<stdio.h>
#include<string.h>
char ascii[26];
int main(int argc, char **argv) {
char *str1 = "turtle";
char *str2 = "tletur";
int len = strlen(str1);
while (len--) {
if (ascii[str1[len]-'a']) {
if (ascii[str1[len]-'a'] != str2[len]-'a')
break;
}
else ascii[str1[len]-'a'] = (str2[len]-'a');
}
if (len == 0xFFFFFFFF)
printf ("ISOMORPHIC");
else
printf ("NOT ISOMORPHIC");
return (0);
}
public static boolean isomorphic(String s1, String s2){
if(s1==null || s2==null || s1.length()!=s2.length())
return false;
int[] c1=new int[26];
int[] c2=new int[26];
Arrays.fill(c1,0);
Arrays.fill(c2,0);
for(int i=0;i<s1.length();i++){
int index1=s1.charAt(i)-97;
int index2=s2.charAt(i)-97;
if(c1[index1]==0 && c2[index2]==0)
{
c1[index1]=s2.charAt(i);
c2[index2]=s1.charAt(i);
}else if(c1[index1]!=0 && c2[index2]!=0){
if(c1[index1]!=s2.charAt(i) || c2[index2]!=s1.charAt(i))
return false;
}else
return false;
}
return true;
}
Here's a simpler solution, check it out and do comment if any flaw
#include<conio.h>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
//isomorphic words
char str1[20],str2[20],str3[20],letter1,letter2;
int len1,len2,i=0,j;
gets(str1);
gets(str2);
strcpy(str3,str2);
len1=strlen(str1);
len2=strlen(str2);
if(len1!=len2)
cout<<"not isomorphic";
else
{
while(i<len1)
{
letter1=str1[i];
letter2=str2[i];
//replace all letter2 in str2 by letter1
for(j=0;j<len1;j++)
if(str3[j]==letter2)
str2[j]=letter1;
i++;
}
}
if(strcmp(str1,str2)==0)
cout<<"isomorphic";
else
cout<<"not isomorphic";
getch();
return(0);
}
public class Isomorph {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String first = scanner.next();
String second = scanner.next();
char[] firstCharArray = first.toCharArray();
char[] secondCharArray = second.toCharArray();
if (firstCharArray.length == secondCharArray.length) {
int[] firstNumberArray = convertToNumberArray(firstCharArray);
int[] secondNumberArray = convertToNumberArray(secondCharArray);
System.out.println("firstNumberArray " + Arrays.toString(firstNumberArray) );
System.out.println("secondNumberArray " + Arrays.toString(secondNumberArray) );
if (Arrays.equals(firstNumberArray, secondNumberArray)) {
System.out.println(true);
} else {
System.out.println(false);
}
} else {
System.out.println(false);
}
}
private static int[] convertToNumberArray(char[] charArray) {
int[] numberArray = new int[charArray.length];
Map<String,Integer> hashMap = new HashMap<String, Integer>();
for (int i = 0; i < charArray.length; i++) {
String character = String.valueOf(charArray[i]);
if (hashMap.containsKey(character)) {
int number = hashMap.get(character);
numberArray[i] = number;
} else {
hashMap.put(character, i);
numberArray[i] = i;
}
}
return numberArray;
}
}
{{
public static boolean isStringIsoMorphic(String str1, String str2){
if(str1.length()!=str2.length())
return false;
int len=str1.length();
//declaring two arrays to keep count of position of each char encountered
int[] str1arr = new int[256];
Arrays.fill(str1arr, -1);
int[] str2arr = new int[256];
Arrays.fill(str2arr, -1);
for(int i=0;i<len;i++){
if(str1arr[str1.charAt(i)]==-1){
if(str2arr[str2.charAt(i)]!=-1){
return false;
}else{
str1arr[str1.charAt(i)]=i;
str2arr[str2.charAt(i)]=i;
}
}else{ // if char in first string has already occurred somewhere
// then look for the char present at same index in str2 previous occurance
System.out.println(str1arr[str1.charAt(i)]);
System.out.println(str2arr[str2.charAt(i)]);
if(str1arr[str1.charAt(i)]!=str2arr[str2.charAt(i)])
return false;
}
}
return true;
}
}}
# Algorithm :
#1. We will 1st use a global mapping of chars from one string to another - to optimze only the keys in the string1 are used
#2. Post this is the comparision & mapping from string 2 & storing in dict keys
#define if two words are isomorphs of each other
def isomorphs(string1, string2):
dict_maps={}
list_chars=map(chr, range(97, 123))
flag=0
#j=0
""" #initizlizing complete dict
for j in list_chars:
dict_maps[j]='0' # this dict will contain mapping of chars from staring 1 to string 2
"""
for j in string1 : #and j not in dict_maps.keys():
dict_maps[j]='0' # have intitialized the dict keys
j=0
if len(string1)==len(string2) :
for i in string2 :
if j < len(string1) : #and len(string1)==len(string2) :
if dict_maps[string1[j]]=='0' and i not in set(dict_maps.values()): # 2nd condition checks if mapping of this value has already occured for another key
dict_maps[string1[j]]=i
elif dict_maps[string1[j]]==i :# a one time mapping has already happened and the char was same
pass
else : # everything else just points that there's a mapping that already exists
flag=1
message= "Strings are not isomorphs of each other "
break
j=j+1
elif len(string1) is not len(string2):
flag =1
message= "mapping not possible - strings are of unequal length - Dictionary map is not initialized" #"strings are isomorphs of each other"
if flag ==0:
message = "strings are isomorphs of each other"
return dict_maps, message
#string1, string2= 'foodiig', 'appijkl'
string1, string2= 'foodf', 'appik'
dict_maps, message =isomorphs(string1, string2)
print " string 1 %s , string2 %s \n " %(string1, string2)
print dict_maps, '\n \n ', message
public boolean isIsomorphic(String word1,String word2){
if(word1==null||word2==null) return false;
if(word1.length()!=word2.length()) return false;
Map<Character,Character> isoMap = new HashMap<Character, Character>();
Map<Character,Character> isoMap2 = new HashMap<Character, Character>();
for(int i=0;i<word1.length();i++){
if(isoMap.containsKey(word1.charAt(i))==false&&isoMap2.containsKey(word2.charAt(i))==false){
isoMap.put(word1.charAt(i),word2.charAt(i));
isoMap2.put(word2.charAt(i),word1.charAt(i));
}
else{
char mappedV1=isoMap.containsKey(word1.charAt(i))==true?isoMap.get(word1.charAt(i)):'0';
char mappedV2 =isoMap2.containsKey(word2.charAt(i))==true?isoMap2.get(word2.charAt(i)):'0';
if(mappedV1!=word2.charAt(i)||mappedV2!=word1.charAt(i)) return false;
}
}
return true;
}
Think in terms of a substitution cipher. String1 is the input, we apply a cipher and we get the string2. The problem is can we find a substitution cipher or in other words, are the strings isomorphic.
To check if two stings are isomorphic, one would not have keep counts. Below O(1) space implementation(bitVector implementation) that works for alphabets.
public class Isomorphic {
public boolean isIsomorphic(String word1, String word2){
long bitMap1 = 0;
long bitMap2 = 0;
long mask1 = 0;
long mask2 = 0;
for (int i=0;i<word1.length();i++){
long res1,res2;
//left shift 1, the ascii value amount of times
mask1 = 1 << (int)(word1.charAt(i));
mask2 = 1 << (int)(word2.charAt(i));
//XOR the mask
res1 = bitMap1 ^ mask1 ;
res2 = bitMap2 ^ mask2 ;
//either both have to be 0 or both have to be non-zero
if((res1>0 && res2>0) || (res1==0&& res2==0)){
bitMap1|= mask1;
bitMap2|= mask2;
continue;
}
return false;
}
return true;
}
}
use hashmap to form one-to-one relationship btw 2 chars
public boolean isIsomorphic(String str1, String str2){
if(str1.length() != str2.length()){
return false;
}
HashMap<Character, Character> hashmap = new HashMap<Character, Character>();
for(int i=0;i<str1.length();i++){
Character a = new Character(str1.charAt(i));
Character b = new Character(str2.charAt(i));
if(hashmap.get(a) == null && hashmap.get(b)==null){
hashmap.put(a,b);
if(a!=b){
hashmap.put(b,a);
}
}
if((hashmap.get(a)==null && hashmap.get(b)!=null) ||
(hashmap.get(a)!=null && hashmap.get(b)==null)){
return false;
}
}
return true;
}
public class Isomorphic {
public static boolean isIsomorphic(String a, String b) {
if(a.length() != b.length()) return false;
if(a == null || b == null) return false;
Map<Character,Character> mappings = new HashMap<Character,Character>();
for(int i = 0; i < a.length(); i++) {
char key = a.charAt(i);
char currentMapping = b.charAt(i);
if(mappings.containsKey(key)) {
char prevMapping = mappings.get(key);
if(prevMapping != currentMapping) return false;
}
else if(mappings.containsValue(currentMapping)) return false;
else mappings.put(key, currentMapping);
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(Isomorphic.isIsomorphic("foo", "app"));
System.out.println(Isomorphic.isIsomorphic("foo", "pap"));
System.out.println(Isomorphic.isIsomorphic("foe", "app"));
System.out.println(Isomorphic.isIsomorphic("ab", "ba"));
}
}
simple c++ code :)
#include<iostream>
#include<conio.h>
#define MAX 100
#include<string.h>
using namespace std;
int isomorphic(string s,string t)
{
int i,j,count=0;
int n=s.length();
char ch[26];
for(i=0;i<26;i++)
ch[i]=48;
int f[26]={0};
for(i=0;i<n;i++)
{
if(ch[s[i]-97]=='0' && f[t[i]-97]==0)
{
ch[s[i]-97]=t[i];
f[t[i]-97]=1;
count++;
}
else
{
if(t[i]==ch[s[i]-97])
{
count++;
}
}
}
if(count==n)
return 1;
else
return 0;
}
int main()
{
string s,t;
cin>>s>>t;
int r=isomorphic(s,t);
cout<<r;
getch();
}
public boolean isIsomorphic(String firstWord, String secondWord) {
if (firstWord.length() != secondWord.length()) return false;
HashMap<Character, Character> map = new HasMap<>();
for (int i = 0; firstWord.length(); i++) {
if (!map.containsKey(firstWord.charAt(i)) {
map.put(firstWord.charAt(i), secondWord.charAt(i));
} else {
if (secondWord.charAt(i) != map.getValue(firstWord.charAt(i))) return false;
}
}
return true;
}
The coloring approach that is the top answer works, but can be made more efficient. This JavaScript code will typically take less than n comparisons, and at most n.
function arePalindromes (str1, str2) {
var letterCodes1 = {};
var letterCodes2 = {};
var letterCount1 = 0;
var letterCount2 = 0;
if (str1.length != str2.length) return false;
for(i in str1) {
var char1 = str1[i];
var char2 = str2[i];
if(!letterCodes1[char1]) letterCodes1[char1] = ++letterCount1;
if(!letterCodes2[char2]) letterCodes2[char2] = ++letterCount2;
var code1 = letterCodes1[char1];
var code2 = letterCodes2[char2];
if(code1 != code2) return false;
}
return true;
};
var actual = [
arePalindromes("foo","app"),
arePalindromes("offa","appe"),
arePalindromes("offa","offa"),
arePalindromes("foo","apple"),
arePalindromes("foof","foaf")
];
var expected = [
true,
true,
true,
false,
false
];
JSON.stringify(actual)==JSON.stringify(expected) ? "TESTS PASS": "TESTS FAIL";
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) return false;
Set<Character> set = new HashSet<Character>();
boolean isomorphic = true;
Map<Character, Character> map = new HashMap<Character, Character>();
for (int i = 0; i < s.length(); ++i) {
if (!map.containsKey(s.charAt(i))) {
if (set.contains(t.charAt(i))) {
isomorphic = false;
break;
} else {
map.put(s.charAt(i), t.charAt(i));
set.add(t.charAt(i));
}
} else {
if (map.get(s.charAt(i)) != t.charAt(i)) {
isomorphic = false;
break;
}
}
}
return isomorphic;
}
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) return false;
Set<Character> set = new HashSet<Character>();
boolean isomorphic = true;
Map<Character, Character> map = new HashMap<Character, Character>();
for (int i = 0; i < s.length(); ++i) {
if (!map.containsKey(s.charAt(i))) {
if (set.contains(t.charAt(i))) {
isomorphic = false;
break;
} else {
map.put(s.charAt(i), t.charAt(i));
set.add(t.charAt(i));
}
} else {
if (map.get(s.charAt(i)) != t.charAt(i)) {
isomorphic = false;
break;
}
}
}
return isomorphic;
}
static boolean findIsomorphic( String str1, String str2 ) {
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
Set<Character> set = null;
for( int i = 0 ; i< ch1.length; i++ ) {
Character ch = ch1[i];
if(map.containsKey(ch)) {
Set<Character> s = map.get(ch);
Character setCh = ch2[i];
if(!s.contains(setCh)){
s.add(setCh);
}
}
else {
set = new HashSet<Character>();
set.add(ch2[i]);
map.put(ch, set);
}
}
Set<Character> keySet = map.keySet();
Iterator<Character> it = keySet.iterator();
Boolean bool = true;
while( it.hasNext() ) {
Character ch = it.next();
Set<Character> finalSet = map.get(ch);
if( finalSet.size() > 1 ) {
bool = false;
}
}
return bool;
}
package practice.sort;
import java.util.ArrayList;
import java.util.HashMap;
public class IsomorphicWords {
public static void main(String args[]) {
final String s1 = new String("for");
final String s2 = new String("app");
final boolean isIsomorphic = checkIfIsomorphic(s1, s2);
System.out.println("Isomorphic results for: " + s1 + " and " + s2
+ " : " + isIsomorphic);
}
public static boolean checkIfIsomorphic(String s1, String s2) {
if (null == s1 || null == s2 || (s1.length() == 0 || s2.length() == 0)) {
return false;
} else if (s1.length() == 0 && s2.length() == 0) {
return true;
}
if (encode(s1).equalsIgnoreCase(encode(s2))) {
return true;
} else {
return false;
}
}
public static String encode(String s) {
// create a map, and insert the char and its first occurence index.
final HashMap<Character, String> map = new HashMap<Character, String>();
final ArrayList<String> listOfIndices = new ArrayList<String>();
for (int i = 0; i < s.length(); i++) {
final char c = s.charAt(i);
if (!map.containsKey(c)) {
map.put(c, String.valueOf(i));
listOfIndices.add(String.valueOf(i));
} else {
final String index = map.get(c);
listOfIndices.add(index);
}
}
final StringBuilder str = new StringBuilder(listOfIndices.toString());
return str.toString();
}
}
package practice.sort;
import java.util.ArrayList;
import java.util.HashMap;
public class IsomorphicWords {
public static void main(String args[]) {
final String s1 = new String("for");
final String s2 = new String("app");
final boolean isIsomorphic = checkIfIsomorphic(s1, s2);
System.out.println("Isomorphic results for: " + s1 + " and " + s2
+ " : " + isIsomorphic);
}
public static boolean checkIfIsomorphic(String s1, String s2) {
if (null == s1 || null == s2 || (s1.length() == 0 || s2.length() == 0)) {
return false;
} else if (s1.length() == 0 && s2.length() == 0) {
return true;
}
if (encode(s1).equalsIgnoreCase(encode(s2))) {
return true;
} else {
return false;
}
}
public static String encode(String s) {
// create a map, and insert the char and its first occurence index.
final HashMap<Character, String> map = new HashMap<Character, String>();
final ArrayList<String> listOfIndices = new ArrayList<String>();
for (int i = 0; i < s.length(); i++) {
final char c = s.charAt(i);
if (!map.containsKey(c)) {
map.put(c, String.valueOf(i));
listOfIndices.add(String.valueOf(i));
} else {
final String index = map.get(c);
listOfIndices.add(index);
}
}
final StringBuilder str = new StringBuilder(listOfIndices.toString());
return str.toString();
}
}
boolean isIsomorphic(String s, String t)
{
if(s.length() != t.length())
return false;
if(s == null || t == null)
return false;
if(s.length() == 0 && t.length() == 0)
return true;
HashMap<Character,Character> map = new HashMap<Character,Character>();
for(int i=0; i<s.length();i++)
{
if(map.size() != 0 && map.containsKey(s.charAt(i)))
{
if(map.get(s.charAt(i)) != t.charAt(i))
return false;
}
else
{
if(map.containsValue(t.charAt(i)))
return false;
map.put(s.charAt(i),t.charAt(i));
map.put(t.charAt(i),s.charAt(i));
}
}
return true;
}
boolean isIsomorphic(String s, String t)
{
if(s.length() != t.length())
return false;
if(s == null || t == null)
return false;
if(s.length() == 0 && t.length() == 0)
return true;
HashMap<Character,Character> map = new HashMap<Character,Character>();
for(int i=0; i<s.length();i++)
{
if(map.size() != 0 && map.containsKey(s.charAt(i)))
{
if(map.get(s.charAt(i)) != t.charAt(i))
return false;
}
else
{
if(map.containsValue(t.charAt(i)))
return false;
map.put(s.charAt(i),t.charAt(i));
map.put(t.charAt(i),s.charAt(i));
}
}
return true;
}
public static bool IsIsomorphic(string s1, string s2)
{
if(string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) return false;
if(s1.Length != s2.Length) return false;
Dictionary<char, char> charHash = new Dictionary<char, char>();
for(int i=0; i< s1.Length;i++){
char c1 = s1[i];
char c2 = s2[i];
Console.WriteLine("c1 & c2 "+c1 + " "+c2);
if(!charHash.ContainsKey(c1))
{
charHash.Add(c1, c2);
}
if(charHash.ContainsKey(c1)) {
if(c2 != charHash[c1]){
Console.WriteLine("c2 & charHash[c1] "+c1 + " "+charHash[c1]);
return false;
}
}
}
return true;
}
I did this in Java:
import java.util.*;
public class IsomorphicStrings1
{
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Enter two words separated by a space: ");
String one = in.next();
String two = in.next();
System.out.println(isIsomorphicOne(one, two));
in.close();
}
private static boolean isIsomorphicOne (String str1, String str2) {
boolean result = true;
if (str1.length() != str2.length()) {
return false;
}
int length = str1.length();
for (int i = 0;i < length;i++) {
if (str1.indexOf(str1.charAt(i)) != str2.indexOf(str2.charAt(i))) {
return false;
}
}
return result;
}
}
import java.util.*;
public class IsomorphicStrings1
{
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Enter two words separated by a space: ");
String one = in.next();
String two = in.next();
System.out.println(isIsomorphicOne(one, two));
in.close();
}
private static boolean isIsomorphicOne (String str1, String str2) {
boolean result = true;
if (str1.length() != str2.length()) {
return false;
}
int length = str1.length();
for (int i = 0;i < length;i++) {
if (str1.indexOf(str1.charAt(i)) != str2.indexOf(str2.charAt(i))) {
return false;
}
}
return result;
}
}
/* Time complexity = O(n)*/
public static boolean isIsomorphic (String s1 , String s2){
if (s1 == null || s2 == null){
throw new IllegalArgumentException();
}
if (s1.length() != s2.length()){
return false;
}
HashMap<Character, Character> map = new HashMap<>();
for (int i = 0 ; i < s1.length(); i++){
if (!map.containsKey(s1.charAt(i))){
if(map.containsValue(s2.charAt(i))){
return false;
}
else{
map.put(s1.charAt(i), s2.charAt(i));
}
}
else{
if( map.get(s1.charAt(i)) != s2.charAt(i)){
return false;
}
}
}
return true;
}
/* Time complexity = O(n)*/
public static boolean isIsomorphic (String s1 , String s2){
if (s1 == null || s2 == null){
throw new IllegalArgumentException();
}
if (s1.length() != s2.length()){
return false;
}
HashMap<Character, Character> map = new HashMap<>();
for (int i = 0 ; i < s1.length(); i++){
if (!map.containsKey(s1.charAt(i))){
if(map.containsValue(s2.charAt(i))){
return false;
}
else{
map.put(s1.charAt(i), s2.charAt(i));
}
}
else{
if( map.get(s1.charAt(i)) != s2.charAt(i)){
return false;
}
}
}
return true;
}
Hash <char, firstseenindex> for each string.
- urik on bb November 07, 2013The encoding of first seenindices shud match.
E.g. Foo and app both encode to 011
Abcd and hole both encode to 0123
Hate and hell do not match
As encodings are 0123 and 0122
Shud work.