Any one get accepted using Python? TLE on sand->acne

  • 0

    Maybe I suck at doing this, but using cProfile module locally the only thing takes time is to build the graph and compare between strings(which run around 3mil times in TLE test data). I am currently trying to see if I can speed up the compare, but it usually means even slower code if the string is too short.

    My compare is just looping through and check if a[i]!=b[i], and if there are 2 of those return right away because you no longer need to check the following chars. If I can cut compare time more, say half on average, I can cut another 30~40% time off my current solution. I've thought of using bitwise operation and build dictionary to check, which is linear time and very efficient, but that would only support up to 6 char length if there is a efficient way to do my own 26 based system.

    The other place to reduce run time is graph building, which I manage to get rid of around .1 mil compare calls, but still not sufficient and not really cut the time consuming part.(where the tree expands most around 3rd to 4th depth). But if I try to cut corner more, the answer are no longer guaranteed to be correct. Especially in case where shortest answer also contains strings that are totally different from start and end.

    So I'm here to not asking for answer, but to see if anyone using python and get accepted yet. If so I could continue on and give more thought of my approach.

  • 0

    stuck at "cet" -> "ism"
    ---- update ---
    now advance to "charge", "comedo"
    ---- update ---
    now to "nape", "mild"

  • 1

    Just passed the test, but I've to say, Python is slow and you have optimize it to pass.

    37 / 37 test cases passed.
    Status: Accepted
    Runtime: 2568 ms
    Submitted: 0 minutes ago

  • 0

    Could you please provide more information about how to optimize it?..

Log in to reply

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