# Determine if two strings with unrecognized letters are from the same text

Given two strings S and T of N=>1 and M=>1 characters, respectively, with unrecognized letters (an unrecognized letter is marked by "?", for brevity, every group of K consecutive "?" characters is replaced by the decimal representation of integer K (without single zero or leading zeros)), you need to know if these two strings can be from the same text.

Example 1: S = "A2Le" , T= "2pL1" could have been obtained as scans of the word "AppLe". Example 2: S = "ba1" , T= "1Ad" could not have been obtained from the same text, as the second letter of each text is different.

Write a function public boolean Solution(String S, String T); that given two strings determines whether strings S and T can be obtained from the same text.

My solution is as follow and I would like to know if it can be improved or done in a better way.

public boolean isSameText(String s, String t) {
// count length by adding the sum of digits and the sum of letters
int LS = countLength(s);
int LT = countLength(t);
// check if the two strings have not the same length
if (LT != LS)
return false;
// determine each identified letter position in String s
// determine each identified letter position in String t
Map<Integer, Character> mapLettersT = findLettersPos(t);
boolean result = true;
//check if recognized letters are positioned the in the same place in
// both Strings
return false;
return result;
}

public int countLength(String s) {

int sumDigits = 0;
int sumLetter = 0;
char[] charArray = s.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if (Character.isLetter(charArray[i]))
sumLetter++;
else
sumDigits = sumDigits + Character.getNumericValue(charArray[i]);
}
return sumDigits + sumLetter - 1;
}

public Map<Integer, Character> findLettersPos(String s) {
Map<Integer, Character> mapLettersPos = new HashMap<Integer, Character>();
// difference between chars position with consideration of numeric
// number
int diff = 0;
for (int i = 0; i < s.length(); i++) {

// here have to check if there is a digit before
if (Character.isLetter(s.charAt(i)))
if (diff > 0)
mapLettersPos.put(i + diff - 1, s.charAt(i));
else
mapLettersPos.put(i, s.charAt(i));
else {
diff += Character.getNumericValue(s.charAt(i));

int j = i + Character.getNumericValue(s.charAt(i));
if(i+1 < s.length())
mapLettersPos.put(j, s.charAt(i + 1));
i = i + 1;
}
}
return mapLettersPos;
}

public boolean checkSamePos(Map<Integer, Character> map1, Map<Integer, Character> map2) {
for (int i = 0; i < map1.keySet().size(); i++) { // use iterator instead
// of for
if (map1.containsKey(i) && map2.containsKey(i)) {
if (map1.get(i).equals(map2.get(i)))
continue;
return false;
}
}
return true;
}

• Welcome to Code Review, your first post looks good, you should get some good answers! – ferada Feb 17 '17 at 11:34

Your solution seems to be too complicated for the problem.

If you first expand your strings to contain sequences of ? instead of the numeric representations like this, the check for equality becomes much simpler.

public String expand(String s) {
final StringBuilder expanded = new StringBuilder();

for (int i = 0; i < s.length(); i++) {
if (Character.isLetter(s.charAt(i))) {
expanded.append(s.charAt(i));
} else {
for (int j = 0; j < Character.getNumericValue(s.charAt(i)); j++) {
expanded.append('?');
}
}
}

return expanded.toString();
}


Now "A2Le" is "A??Le" and "2pL1" is "??pL?"

You can just iterate through the strings character by character and check for equality, if not at least one of them is the wildcard ?.

public boolean Solution(String s, String t) {
final String expandedS = expand(s);
final String expandedT = expand(t);

if (expandedS.length() != expandedS.length()) {
return false;
}

for (int i = 0; i < expandedS.length(); i++) {
if (expandedS.charAt(i) != '?' && expandedT.charAt(i) != '?'
&& expandedS.charAt(i) != expandedT.charAt(i)) {
return false;
}
}

return true;
}


The solution becomes apparent if you align your expanded strings like this:

"A??Le"
"??pL?"


matches, but

"ba?"


does not match.

In your method countLength() you do not need your char[] charArray, you can just use the charAt() method of the String class directly.

## Use of Braces

I strongly recommend using { } even for single line control statements. You make use code like this

if (diff > 0)
mapLettersPos.put(i + diff - 1, s.charAt(i));


quite a lot and especially nested ifs become hard to read and are a source of many errors.

Consider the decimal representation of integer K (without single zero or leading zeros).

The case A10Le and AppppppppppLe should return true.

I modify the Maximilian Köstler's code as follows:

public static String expand(String s) {
final StringBuilder expanded = new StringBuilder();
boolean isNeedExpandQestionMark = false;
int K = 0;
char c = '0';

for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (Character.isLetter(c)) {
if (isNeedExpandQestionMark){
for (int j = 0 ; j < K ; j++) {
expanded.append('?');
}
isNeedExpandQestionMark = false;
}
expanded.append(c);
} else {
if(isNeedExpandQestionMark){
K = K * 10 + Character.getNumericValue(c);
} else {
K = Character.getNumericValue(c);
}
isNeedExpandQestionMark = true;
}
}
// Case: last part of char is demical number
if (isNeedExpandQestionMark){
for (int j = 0 ; j < K ; j++) {
expanded.append('?');
}
}
return expanded.toString();
}
public static boolean Solution(String s, String t) {
final String expandedS = expand(s);
final String expandedT = expand(t);

if (expandedS.length() != expandedT.length()) {
return false;
}

for (int i = 0; i < expandedS.length(); i++) {
if (expandedS.charAt(i) != '?' && expandedT.charAt(i) != '?'
&& expandedS.charAt(i) != expandedT.charAt(i)) {
return false;
}
}
return true;
}