CODEWITHSUNDEEP
javaalgorithm
user5182503
user5182503

Reputation:

Java: replacement in a string according to multiple rules

I have the following task. There is a string. I must do replacement in it according to 6 rules till it is possible to make a replacement in a string.

The solution I found is below. It works right. The problem is that its performance is low. How else can I make replacement according to multiple rules? Is there any algorithm?

P.S. This task is from codility site. I got 100% correctness and 25% performance for my solution. 

class Test {

    private Map<String,String> rules;

    private void initRules(){
        rules=new HashMap<>();
        rules.put("AB", "AA");
        rules.put("BA", "AA");
        rules.put("CB", "CC");
        rules.put("BC", "CC");
        rules.put("AA", "A");
        rules.put("CC", "C");
    }

    public String test(String S) {
        initRules();
        loop:while(true){
            String oldString=S;
            for (Map.Entry<String, String> rule : rules.entrySet())
            {
                S=S.replace(rule.getKey(), rule.getValue());
            }
            if (oldString==S){
                break loop;
            };
        }
        return S;
    }
}

 public class NewMain {

    public static void main(String[] args) {
        Test test=new Test();
        System.out.println("Result:"+test.test("ABBCC"));;
    }

}

Upvotes: 5

Views: 7956

Answers (6)

virsha
virsha

Reputation: 1168

I prefer do while loop instead of recursion :

Here is the answer : 

public String stringReduce(String input) {
    String previous;
    do {
        previous = input;
        input = input.replace("AA", "A").replace("CC", "C").replace("BC", "C").replace("CB", "C")
                .replace("BA", "A").replace("AB", "A");
    } while (!previous.equals(input));
    return input;
}

Upvotes: 1

eranmapa
eranmapa

Reputation: 31

You can impliment a recursive algorythm for this. Then you can reduce the rules and apply. For instance AB -> AA, AA -> A then AB->A Then the answer would be

public static String stringReduce(String s){
  String transformed = s.replace("AA", "A").replace("CC", "C")
   .replace("BC", "C").replace("CB", "C").replace("BA", "A")
   .replace("AB", "A");

  if(transformed.equals(s)){
    return transformed;
  }
  else{
    return stringReduce(transformed);
  }
}

Upvotes: 2

Prabakar Veer
Prabakar Veer

Reputation: 1

Here is my C# Solution:

public static string solution(string S)
    {
        return Getreplace(S);
    }

    public static string Getreplace(string input)
    {
        string retval = input.Replace("AB", "AA")
                    .Replace("BA", "AA")
                    .Replace("CB", "CC")
                    .Replace("BC", "CC")
                    .Replace("AA", "A")
                    .Replace("CC", "C");

        if (input == retval)
            return retval;
        else
            return Getreplace(retval);
    }

Upvotes: 0

Raymond Chenon
Raymond Chenon

Reputation: 12712

I followed the reasoning of @vish4071 .

I look for sub-Strings of "B" and "A" only , I know this segment will be become "A" . Same for sub-Strings "B" and "C" only.

"BAABBABAB" becomes "A" due to replace("AB" by "AA"),replace("BA" by "AA"), replace("AA" by "A")

input: "BBBAABABBBCCBCBBCACB"

"BBBAABABBB" "CCBCBBC" "A" "CB"

"A" "C" "A" "C"

output : "ACAC"

The two algorithms keep track when the sub String "A" changes from/to "C". I append the known previous char. Because change detection is based on "A" to "C" or "C" to "A", you don't previous char in the first sub-string. After the loop , you have to append with last previous char.

Runtime complexity : O(n)

Space complexity : O(1)

Here is the implementation in Java.

  public static String solution(String S) {

        final char C = 'C';
        final char A = 'A';

        // if contains only B return itself
        if(!S.contains("A") || !S.contains("C")) return S;

    String res = "";
    boolean hasLetterChanged = false;
    char prevChar = 'D';
    for(char c : S.toCharArray()){
        if (c == A){
            if (prevChar == C){hasLetterChanged = true;}
        }else if(c == C){
            if (prevChar == A){hasLetterChanged = true;}
        }
        if(hasLetterChanged){
            res = res + prevChar;
            hasLetterChanged = false;
        }
        if(c == A || c == C){
            prevChar = c;
        }
    }

    return res + prevChar;
}

Here is the implementation in Python 2.7 ( compatible with 3x) .

def solution(S):
    if not(S.__contains__('C') and S.__contains__('A')): return S

    has_char_changed = False
    prev_char = 'B'
    A = 'A'
    C = 'C'
    res = ""
    for c in S:
        if c == A:
            if prev_char == C:
                has_char_changed = True
        elif c == C:
            if prev_char == A:
                has_char_changed = True

        if has_char_changed:
            res = res + prev_char
            has_char_changed = False

        if c == A or c == C:
            prev_char = c

    return res + prev_char


if __name__ == '__main__':
    assert solution("ABBCC") == "AC"
    assert solution("BCBCABB") == "CA"
    assert solution("BBBAABABBBCCBCBBCACB") == "ACAC"
    assert solution("BBBBBBB") == "BBBBBBB"

Upvotes: 0

Atul
Atul

Reputation: 71

My Solution in python using the regular expression.

Explanation: if input is "ABACAABBCA".

First while iteration: Will replace AB -> A, AA->A, BC->C. The value of strng is "AACACA"

Second while iteration: Will replace AA->A. The value of strng is "ACACA"

Third while iteration: Nothing to replace so will exit and return the final substituted string (strng). Let me know if any improvements or corrections needed. 

def solution(strng):
  prevS=""
  subst={"AB":"A","BA":"A","CB":"C","BC":"C","AA":"A","CC":"C"}
  subs=lambda st:subst[st.group(0)]
  while prevS!=strng:
      prevS=strng
      strng=re.sub(r'(([A][BA])|([B][A])|([CB][C])|([C][B]))',subs,strng)
  return strng

Upvotes: 0

vish4071
vish4071

Reputation: 5277

Here is an algorithm you can use:

Assumption: String consists of only (A,B,C)

If string is composed of B's only (no A/C), output = input string.

Otherwise:

Divide the string in the following way. If a substring consists of (B,A) or (B,C), divide them. Replace with A and C respectively. That will be the answer.

eg. Let the string be: "BBBAABABBBCCBCBBCACB". This will be divided as:

"BBBAABABBB" "CCBCBBC" "A" "CB"

And this will result in output string as: ACAC

Basically, just ignore all B's and replace clusters of A's with A and clusters of C's with C.

Upvotes: 5

Related Questions