Compressing a string

Question

The task is to compress a string.

eg. "abcbcdabcbcd"

Here as you can see some characters are repeated, so it can be compressed.

"abcbcdabcbcd" -> "(a(bc2)d2)$"

'$' denotes end of string.

My code:

import java.util.*;
class compress
{
 public static void main(String[] ar)
 {
 System.out.print(">> ");
 Scanner sc = new Scanner(System.in);
 String s = sc.next();
 System.out.println(compress(s));
 }
 public static String compress(String s)
 {
 String a = "";
 boolean found = false;
 for(int l = 0; l < s.length(); l++)
 {
 for(int i = l; i < s.length(); i++)
 {
 String t = s.substring(l,i+1);
 try
 {
 int q = 1;
 int st = i+1;
 String p = "";
 while(st + t.length() <= s.length())
 {
 p = s.substring(st,st+t.length());
 if(p.equals(t))
 q++;
 else break;
 st += t.length();
 }
 if(q != 1)
 {
 a += "(" + compress(t) + q + ")";
 l = st-1;
 i = st;
 found = true;
 }
 }catch(Exception e){}
 }
 if(!found)
 a += s.charAt(l);
 found = false;
 }
 return a;
 }
}

Please help to improve my code and suggest a better solution.

• Mathieu Guindon: Is the double-indent of the first 2 lines of void main a paste glitch? FWIW I'm not buying catch(Exception e){}.
• user2369284: It's a paste glitch. What is FWIW?
• Mathieu Guindon: For what it's worth :)
• Simon Forsberg: Daniel Cook answered your previous question 37 minutes before you asked this one. He told you to use better variable names. I won't review this until you use better variable names. That is why I am downvoting this. Please edit it and use better variable names and I will gladly review it and give it an upvote.
• Malachi: not sure I know what format is coming out, but shouldn't (a(bc2)d2)$ be something like ((a(bc2)d)2)$ ? logically I would think that you want the pattern a(bc2)d to repeat twice, not have d repeat twice at the end.

Answer 1

import.util.*

One thing I have notice from reading other Java Reviews is that you don't want to import more libraries than you have to, really this goes for any language I would think. so figure out what you need in java.util and import that. I know that in C or C++ there is a library that when imported really annoys other programmers, but I can't remember what it is, not sure if there is a similar library in Java though.

---

If you aren't going to do anything with the exception don't catch it. don't use a Try ... Catch let it tell you what you are doing wrong every time so that you can code it right. this should give you a little bit of performance.

not sure what type of competitive programming that you are doing, but in some competitions they go by number of lines so removing the Try Catch would save you lines.

---

From my Comment

shouldn't (a(bc2)d2)$ be something like ((a(bc2)d)2)$ ? logically I would think that you want the pattern a(bc2)d to repeat twice, not have d repeat twice at the end.

I hope that makes sense.

---

Eliminate an If Statement

this code here can be changed

while(st + t.length() <= s.length())
{
 p = s.substring(st,st+t.length());
 if(p.equals(t))
 q++;
 else break;
 st += t.length();
}
if(q != 1)
{
 a += "(" + compress(t) + q + ")";
 l = st-1;
 i = st;
 found = true;
}

to something like this:

while(st + t.length() <= s.length())
{
 p = s.substring(st,st+t.length());
 if(p.equals(t))
 {
 q++;
 a += "(" + compress(t) + q + ")";
 st += t.length();
 l = st-1;
 i = st;
 found = true;
 }
 else break;
}

because if you increment q it will not be equal to 1, and the rest of the logic stays the same, this should also increase the performance.

---

another thing that I just noticed, and this may go against the whole competitive programming thing, and may make the code more unreadable but you are adding two variables together the same way multiple times.

create another variable perhaps stt and use that to represent st+t.length then you can write it like this.

int st = i+1;
int stt = st + t.length
while(stt <= s.length())
{
 p = s.substring(st,stt);
 if(p.equals(t))
 {
 q++;
 a += "(" + compress(t) + q + ")";
 l = st-1;
 i = stt;
 found = true;
 }
 else break;
}

Here we removed an assignment and redundancy by creating another variable called stt (whatever that is)

Answer 2

Your naming is awful. Even void main(String[] args) has been butchered to void main(String[] ar)... and the only identifier that's more than 2 letters in this code, is called found - which implies a search, but the method is called compress.

What exceptions are you swallowing, and why? I'm no java guru, but an empty catch clause is always a code smell.

The main issue with this code is the naming. Variables should always have meaningful names. Naming doesn't make your code run any better or worse. But writing code that works is usually 20% of the job. Reading (/maintaining) the code is usually the other 80%. You'll thank yourself in 6 months when you go back to this code and you can tell the meaning of q without having to fully understand everything that's going on in that loop.

• user2369284: I am more interested in competitive programming at the moment so short variable names suit me
• Mathieu Guindon: We don't do code golf here. The purpose of CR is to write good code. If you're looking for golfed code, I'm afraid you've knocked the wrong door; please see help center
• Simon Forsberg: @user2369284 The only competition we like here is who writes the best code. Too short variable names = Not the best code. If you are interested in writing short and obfuscated code, Code Golf might be something for you.
• Simon Forsberg: There is no Exception that should be thrown there. Possibly a RuntimeException of some kind, but those shouldn't be caught like that. Ever.
• Claudiu: @user2369284: if you're talking about timed code competitions, you will save more time in the long run by using long variable names. Typing speed is not your bottleneck - thinking speed is, and thinking speed will decrease if your variables are not named properly.