Anagrams!
Hi can someone help me with this? I'm sorry I don't really understand this.
Given a string consisting of lowercase letters and question marks, s1, and another string consisting of lowercase letters, s2, determine whether these two strings could become anagrams by replacing each ? character in s1 with a letter.
Input
1. First string
Constraints
Contains only lowercase letters and/or question marks
2. Second string
Constraints
Contains only lowercase letters
Expected Output:
Enter first string: n?ce
Enter second string: nice
anagram
Given a string consisting of lowercase letters and question marks, s1, and another string consisting of lowercase letters, s2, determine whether these two strings could become anagrams by replacing each ? character in s1 with a letter.
Input
1. First string
Constraints
Contains only lowercase letters and/or question marks
2. Second string
Constraints
Contains only lowercase letters
Expected Output:
Enter first string: n?ce
Enter second string: nice
anagram
what do you not understand?
an anagram is where a random permutation of the letters makes another word.
for example:
eat
ate
tea
are all anagrams of each other.
-- aet is not a real word, but mechanically it is an anagram as well.
sorting helps.
if you had
eat
and
ate
and sorted both strings, you get:
eat -> aet
ate -> aet ... oh look, the sorted strings match!
so far, nothing fancy. now you have a twist, dealing with the ? character.
one way to do it is to not replace it at all.
n?ce has 1 ? character.
you can still do the sort, but now use a special compare that allows up to # of ? characters mismatches (and the sorted ?s will be on one end of the result, easy to count). here, you have 3 matches and 1? to make a 4 letter word. so the answer is yes, it can be done. If you had 2 matches and 1 ?, it will fail, 2+1 is only 3. so x?ce and nice can't match, see?
an anagram is where a random permutation of the letters makes another word.
for example:
eat
ate
tea
are all anagrams of each other.
-- aet is not a real word, but mechanically it is an anagram as well.
sorting helps.
if you had
eat
and
ate
and sorted both strings, you get:
eat -> aet
ate -> aet ... oh look, the sorted strings match!
so far, nothing fancy. now you have a twist, dealing with the ? character.
one way to do it is to not replace it at all.
n?ce has 1 ? character.
you can still do the sort, but now use a special compare that allows up to # of ? characters mismatches (and the sorted ?s will be on one end of the result, easy to count). here, you have 3 matches and 1? to make a 4 letter word. so the answer is yes, it can be done. If you had 2 matches and 1 ?, it will fail, 2+1 is only 3. so x?ce and nice can't match, see?
Last edited on
First test that they are the same length; if they aren't then they definitely aren't anagrams.
Method 1:
For each character in S2:
---if that character exists in S1 then set that character in S1 to blank.
At the end, if S1 is left with only blanks and ? marks then they can be made anagrams.
Method 2 (possibly quicker):
Iterate through each character in S1:
---if that character is not a ?:
------if that character exists in S2 then set that character in S2 to blank;
------else return false.
If you successfully get to the end then return true.
Method 1:
For each character in S2:
---if that character exists in S1 then set that character in S1 to blank.
At the end, if S1 is left with only blanks and ? marks then they can be made anagrams.
Method 2 (possibly quicker):
Iterate through each character in S1:
---if that character is not a ?:
------if that character exists in S2 then set that character in S2 to blank;
------else return false.
If you successfully get to the end then return true.
Last edited on
Topic archived. No new replies allowed.