Why does my code keep causing a time limit exceeded error?


  • 0
    A

    I was coding in Java as follow, but it kept causing time limit exceeded.

      public class Solution {
            public String nextOne(String s) {
                char sym = s.charAt(0);
                int count = 1;
                String result = "";
                for (int i = 1; i < s.length(); i++) {
                    if (sym == s.charAt(i)) {
                        count++;
                    }
                    else {
                        result += count + sym;
                        sym = s.charAt(i);
                        count = 1;
                    }
                }
                result += count + sym;
                return result;
            }
            
            public String countAndSay(int n) {
                if (n <= 0)
                    return null;
                String s = "1";
                for (int i = 1; i < n; i++) {
                    s = nextOne(s);
                }
                return s;
            }
        }
    

    Then, I tried other's code in C++ with the same time complexity. It was accepted...

    class Solution {
    public:
        string nextOne(string s) {
    		string ret = "";
    		char pre =s[0];
    		int count = 1;
    		for(int i = 1; i < s.size(); i ++) {
    			if(s[i]==pre) {
    				count ++;
    			}
                else {
    				char tmp =  count + '0';
    				ret = ret + tmp + pre;
    				pre = s[i];
    				count = 1;
    			}
    		}
    		char tmp =  count + '0';
    		ret = ret + tmp + pre;
    		return   ret;
    	}
        string countAndSay(int n) {
    		string ret = "1";
    		for (int i = 1; i < n; i++)
    			ret = nextOne(ret);
    		return ret;
        }
    };
    

    Is that because Java runs slower than C++? Anyone knows why?


  • 3
    S

    Seems not the OJ's fault.

    Try to change your code from

    result += count + sym;
    

    to

    result += Integer.toString(count) + sym;
    

    Here is some explanation might be helpful.


  • 0
    A

    Hi, thank you for your suggestion. It helps me pass the test. However, I still don't understand why my code doesn't work.
    As I know, Java has overloaded operator + for String class by creating a StringBuilder instance and invoking its append methods. And, there does exist an overload version of append function for int type. It will convert the int value to String anyway.
    So, why these two statements don't do the same work?


  • 0
    Z

    count is int, sym is char.

    It's not a "" + int vs. Integer.toString(int) issue. It's a String + int vs. char + int issue.

    result += "" + count + sym would have worked as well. If you add int and char then the result will be the int value + the ascii value of the char...


  • 0
    A

    agree, good comment.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.