I know this problem may seem obviously trivial for many programming masters, but not for me; actually I was really over-thinking into it and wondering why it's only a 3-point problem.
To the problem contributor: you really got me this time! (if the baffling problem description is intentional)
Anyone has the same feeling?
+1 for Fools' day.
Me too. I was thinking the result of
should be 2.
It seems leetcode consider that less code lines for solution, lower difficulty for problem...
@liupangzi Interesting. However, many hard problems should be finished in linear time, and could be finished in a few lines.
I was over-thinking too...
When I first seem this problem,I consider it should be solved by DP..like longest common subsequence...
I actually got this problem. Below is my thinking step:
- I first considered the special case, two strings are not of same length, it is clearly the longest one is the answer.
- Then for two strings with same length, if anyone of them has a char which the other string does not have, clearly the whole string's length is the answer.
- Then for two strings with same charset, one string is just a combination of chars of another string, I thought about the ordering of chars matters here. Then I got it, if they are not equal, we can quickly decide, which also covers case 2).
Problem Solved, :-)
I was tricked by this problem because
Both strings' lengths will not exceed 100. I was looking for a DP/Backtracking solution, haha
Here is my feeling about why the level of difficulty in Leetcode seems inaccurate sometime:
- There are some problems are classified as Easy, but they are actually not that easy unless you are familiar with some tricks.
- Some Hard problems are marked as Medium or Easy was because the expected runtime weren't strict enough such as a problem can be solved in linear time, but the OJ is happy to accept O(n^2) solution.
There are also some problems that are difficult to judge the hardness:
- I remember there is a problem can be solved by DFS or BFS, the solution should be equally good, but OJ only accept BFS solution, because the test cases are highly biased.
- Personally speaking a recursive solution and iterative solution should be equally good to solve some problems despite a recursive solution will cost extra memory using system stack. However there are some problems only accept a iterative solution in order to get accepted.
@zhengkai2001 Took me 50 mins (and many lines of code) before I saw the 1-line solution :) Although the solution is trivial, I am not quite sure it should be considered Easy.
This problem is nothing but a waste of time. I literally learned nothing from it, after I saw the solutions, feeling like I was f u c k ed by someone.
@lijunray haha, many problems in leetcode are like that.
I don't think the problem is a waste of time. If you solved it right away, then you didn't lose much time, so no harm done. But if you struggled, then you need to analyze why. Did you read the problem carefully, did you stop to understand it well? Also, it may be that there is nothing wrong with going in the wrong direction (like I did) and losing a ton of time. That hurts because everyone's time is precious but that's part of the process.
With that said, I would't give it on a coding interview. You can't bet your evaluation of a candidate on such a tricky problem. I would much rather pick a problem where a solution is fairly obvious, but it's a bit harder to formulate and code correctly. Recursive problems are like that - you need to remember where you are and how to put everything together. If the person is struggling, you can see how they handle that and find their way (even if they don't solve it in the end). If they have practiced a lot and do it quickly, you didn't learn that much about them.
@jrusev I agree with this. I struggled with it for a while before realizing it was trivial, because I didn't think through the possible cases and what was really being asked methodically enough. Probably bad for an interview question, but I guess it was a good learning experience.
In fact, this problem is a logic problem. Although I don't think this kind of questions will appear frequently on interviews, the problem is still meaningful. At least it reminds us reading the question description carefully and thinking of a problem at a high level at first before going to details.
The question should be provided with some meaningful examples. I was thinking too much about the word, "uncommon". What do you mean by "uncommon"? Is it some kind of opposite way to do LCS??? I think this is about "communication skill" rather than algorithm.
So, I was thinking the case "cdef" and "cdnq", wondering why the longest uncommon subsequence for these two is 4 instead of 2?
After seeing the solution and validating with the explanation of the given example, I noticed that I can safely say that:
"The longest uncommon subsequence is "cdef" (or "cdnq"), because "cdef" is a subsequence of "cdef", but not a subsequence of any other strings in the group of two strings. (cdnq)."
This problem is a trap!!! I wouldn't show such problem to a interviewee if only my head was kicked by a donkey.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.