CODEWITHSUNDEEP
java
Maaz053
Maaz053

Reputation: 11

What can be done to optimize the given code

Time limit for give code has to be less than 1.824 seconds.Below given code is exceeding yhe limit.What can I add or replace so that the code gets optimized and runs within the time limit. The following code checks whether the given string is pallindrome or not by removing the 'spaces' and special character from the string.The string mus hold only alphabets after removing special characters. Example: Input: 2 I am :IronnorI Ma, i Ab?/Ba Output: YES YES

CODE:

public static void main (String[] args) throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int T=Integer.parseInt(br.readLine());
    while(T-->0)
    {
        String frog=br.readLine().replaceAll("\\s+","").replaceAll("[^\\w]","");
        String news="";
        char ch;
        for(int i=0;i<frog.length();i++)
        {
            ch=frog.charAt(i);
            news=ch+news;
        }
        if(news.equalsIgnoreCase(frog))
        System.out.println("YES");
        else
        System.out.println("NO");

    }
}

}

Upvotes: 1

Views: 76

Answers (2)

Mead
Mead

Reputation: 100

Use a single regex instead of two, so you don't have to do 2 replaceAll(), and a StringBuilder, since each concatenation creates a new String (strings are immutable)

public static final void main (final String[] args) throws IOException
{
    final BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int T=Integer.parseInt(br.readLine());
    final StringBuilder sb = new StringBuilder();
    String frog;
    while(T-->0)
    {
        frog = br.readLine().replaceAll("\\s+|[^\\w]","");
        for(int i=frog.length()-1;i!=-1;i++)
        {
            sb.append(frog.charAt(i));
        }
        if(sb.toString().equalsIgnoreCase(frog))
        System.out.println("YES");
        else
        System.out.println("NO");
        sb.setLength(0);
    }
}

Upvotes: 0

Ali Elgazar
Ali Elgazar

Reputation: 777

This seems like a homework assignment, so I won't be providing you the code, I'll just direct you on how you can improve your approach.

Your approach is fairly linear, you reverse the string, then you compare the reverse to the original. While this is a correct way of doing it, you're incurring too many operations.

Assuming the string is of length N, The alternative method is simply to loop N/2 times, and each time you compare the ith character to the N-ith character. If any character does not match, print No and break, otherwise keep comparing. If all characters match, print yes.

Mead's solution is practically the same as yours, albeit it cuts down on the initial filtering operation.

Upvotes: 4

Related Questions