5
\$\begingroup\$

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
    Map<Integer, Character> mapLettersS = findLettersPos(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
    if (!checkSamePos(mapLettersS, mapLettersT))
        return false;
    result = checkSamePos(mapLettersT, mapLettersS);
    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;
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review, your first post looks good, you should get some good answers! \$\endgroup\$ – ferada Feb 17 '17 at 11:34
6
\$\begingroup\$

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?"
"?Ad"

does not match.

Additional Remarks

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.

\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.