String metrics alghoritms in Java-CodePudding

I am solving the problem of processing strings in Java. Please help me solve the problem.

Condition of the problem: John has launched his new startup to recognize the clouds he has seen, which he called string A of length N . But suddenly he found out that Sam also launched his cloud recognition startup and called it string B of length N.

More formally, let there be strings A, the name of John's startup, and string B, the name of Sam's startup. Both strings are the same length N. For each position 1 ≤ i ≤ N of string B , you need to calculate the type of match at this position with string A .

If a
Bi=Ai, then in position i the match type must be equal to P (from the word plagiarism).

If Bi≠Ai, but there is another position 1≤j≤N such that Bi=Aj, then in position i
  match type must be equal to S (from the word suspicious).

Note:

 Letters within one line can be repeated.
 Each letter of string A can be used in at most one plagiarism or suspicious match.
 Preference is always given to the plagiarism type.
 In the case of a suspicious match, the leftmost position in row A is always preferred.

. In other positions, the match type must be equal to I (from the word innocent).

Input Format

The first line contains the string

A(1≤∣∣A∣∣≤10^6) is the startup name chosen by John.

The second line contains the string B(|B|=|A|) — the name of Sam's startup.

It is guaranteed that strings A and B
  contain only uppercase latin letters.

Output Format

Output a single line
C(|C|=|B|), where Ci is the match type of the character Bi(1≤i≤|B|):
for type plagiarism Ci= P.

for type suspicious Ci=S.

for type innocentCi=I.

Example 1:

Input      Output

CLOUD     PSIIP
CUPID

Example 2:

Input      Output

ALICE     SPII
ELIBO

Example 3:

Input       Output

ABCBCYA    IPSSPIP
ZBBACAA

Notes:


Explanation for the first test


B1=A1 and B5=A5 , so for positions 1 and 5 the answer is P.

B2≠A2 , but B2=A4, so for position 2 the answer is S.

Letters P and I do not occur in string A, so for positions 3 and 4 the answer is I.


Explanation for the second test:


B2=A2 and B3=A3, so for positions 2 and 3 the answer is P.

B1≠A1 , but B1=A5, so for position 1 the answer is S.

Letters B and O do not occur in string A, so for positions 4 and 5 the answer is I.


Explanation for the third test:


B2=A2 , B5=A5 and B7=A7 so for positions 2, 5 and 7 the answer is P.

B3≠A3 but B3=A2=A4. A2 is already enabled according to B2=A2,

therefore, the correspondence B3=A4 is chosen - for position 3 the answer is S.

B4≠A4 and B6≠A6, but B4=B6=A1=A7.

A7 is already enabled according to B7=A7;

4<6, therefore, for position 4, the correspondence B4=A1 (answer S) is selected;

there are no matches left for position 6 (answer I).

The letter Z does not occur in string A, so for position 1 the answer is I.

A7 is already enabled according to B7=A7;

4<6, therefore, for position 4, the correspondence B4=A1 (answer S) is selected;

there are no matches left for position 6 (answer I).

The letter Z does not occur in string A, so for position 1 the answer is I.

My solution:

public class Solution {
  public boolean backspaceCompare(String s, String t) {
    return formBackSpaceString(s).equals(formBackSpaceString(t));
  }
  
  private String formBackSpaceString(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
      if (c == '#') {
        if (!stack.isEmpty()) {
          stack.pop();
        }
      } else {
        stack.push(c);
      }
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
      sb.append(stack.pop());
    }
    return sb.toString();
  }
public static void main (String[] args){
 }
}

I am bogged down in the logic of this task. I would be grateful for help at least at the pseudocode level.

CodePudding user response：

The code you provided does not seem related to the problem you described.

The problem asks to apply a simple rule for chars (Ai, Bi) from the original string to construct a new string C. There are only three rules:

If Ai == Bi, Ci = "P"
Otherwise, if A contains char Bi, Ci = "S"
Otherwise, Ci = "I"

You can do that in a simple way using stream API:

String problem(String A, String B) {
    // construct a set of all chars in A
    Set<Integer> aChars = A.chars().boxed().collect(Collectors.toSet());

    // apply rules for chars Ai, Bi
    return IntStream.range(0, A.length())
            .mapToObj(i -> A.charAt(i) == B.charAt(i) ? "P" :
                    aChars.contains((int) B.charAt(i)) ? "S" : "I")
            .collect(Collectors.joining());
}

Or, more verbosely, without it:

String problem(String A, String B) {
    Set<Character> aChars = new HashSet<>();
    for (int i = 0; i < A.length(); i  ) {
        aChars.add(A.charAt(i));
    }

    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < A.length(); i  ) {
        if (A.charAt(i) == B.charAt(i)) {
            builder.append("P");
        } else if (aChars.contains(B.charAt(i))) {
            builder.append("S");
        } else {
            builder.append("I");
        }
    }
    return builder.toString();
}