4 lines in Java


  • 38
    public List<String> generatePossibleNextMoves(String s) {
        List list = new ArrayList();
        for (int i=-1; (i = s.indexOf("++", i+1)) >= 0; )
            list.add(s.substring(0, i) + "--" + s.substring(i+2));
        return list;
    }

  • 0
    C

    One less line then my solution but better yet it is less iterations. Well played.


  • 1
    E

    Amazing! I wonder why s.sustring(i+2) doesn't trigger the IndexOutOfBoundsException when the last "++" is on the tail of String s. Let's say "++--++", in last for loop i will be assigned to 4, i+2=6, but index is from 0 to 5, 6 is not larger than s.length() but is bigger than largest index 5......I get so confused about this part......


  • 0

    That simply gives you the empty suffix then. Why would that fail? It's a completely normal and sometimes legitimately needed request.

    You could say the same about "++--++".substring(99), and in fact Python for example lets you do that ('++--++'[99:] works and results in ''). But apparently that's where the Java creators draw the line and say that that's exception-worthy.


  • 0
    E

    Oh, I understand! :-)Thank you, Stefan!


  • 0

    elegant, but performance is a little bit lower than using char bit.


  • 0

    What do you mean with char bit?


  • 0

    I mean use char array to scan one by one instead of indexof. sorry for the wrong words "char bit".


  • 0

    Ah, ok. How did you determine the performance? And can you please show the char array solution that you're comparing this against?


  • 0

    Oh,I just see the different #ms when I submit. Here they are: 456ms, https://leetcode.com/submissions/detail/51544732/, 484ms, https://leetcode.com/submissions/detail/51546693/. Both of them are made in C#. It might be different as Java.


  • 0

    I can't view those, I don't have the permission. Anyway... in Java it gets accepted in 1 ms. It's probably about the same in C# so that the times you got have pretty much nothing to do with the solution runtime but almost 100% represent the judge overhead and its variance. Can you submit each a few more times and post the times?


  • 0

    I just tried this:

    public IList<string> GeneratePossibleNextMoves(string s) {
        IList<string> list = new List<string>();
        for (int j=0; j<1000; j++) {
            list = new List<string>();
            for (int i=-1; (i = s.IndexOf("++", i+1)) >= 0; )
                list.Add(s.Substring(0, i) + "--" + s.Substring(i+2));
        }
        return list;
    }
    

    That does the job 1000 times. Gets accepted in about 745 ms on average. That's about 270 ms over the baseline of about 470 ms. Assuming all 1000 times run about equally fast, that's 0.27 ms per run. Which is a lot less than the baseline and its variance.

    So you really can't tell anything from your measurements.

    You could do the "1000 times" for your char array version as well, though, and then we might see a somewhat meaningful difference.


  • 0

    You are right. I tried a couple of times. the #ms is changed from 452 to 492, more than your solution in c#. Thank you very much for explaining!


  • 3
    V

    Doesn't this perform better than substring?

    public List<String> generatePossibleNextMoves(String s) {
            List<String> answer = new ArrayList<>();
            char[] arr = s.toCharArray();
            for(int i = 0; i < arr.length - 1; i++){
                if(arr[i] == '+' && arr[i+1] == '+'){
                    arr[i] = '-'; arr[i+1] = '-';
                    answer.add(new String(arr));
                    arr[i] = '+'; arr[i+1] = '+';
                }
            }
            return answer;
        }

  • 0

    @Vick.Chen here's a C# version using char array that you may be thinking of. For C# at least this is the best way to avoid any extra string creation, just creates 1 string per found item and only 1 call to create the original char array. As for OJ times, they do vary a lot, wildly sometimes, and I know the C# runtime is usually much slower than other runtimes. Submit your solution a couple times to get a rough idea of how it compares and what the variance is.

        public IList<string> GeneratePossibleNextMoves(string s) {
            char[] chars = s.ToCharArray();
            IList<string> list = new List<string>();
            for (int i = 0; i < chars.Length - 1; i++)
            {
                if (chars[i] == '+' && chars[i+1] == '+')
                {
                    chars[i] = '-';
                    chars[i+1] = '-';
                    list.Add(new string(chars));
                    chars[i] = '+';
                    chars[i+1] = '+';
                }
            }
            return list;
        }
    

  • 0
    F

    @StefanPochmann I also confused about why s.sustring(i+2) doesn't trigger the IndexOutOfBoundsException. I tried s.indexOf(99) where s = "++++". It returns java.lang.StringIndexOutOfBoundsException: String index out of range: -95.
    But in your code, the last loop will just return a empty suffix but not error when index+2 greater than s.length().


Log in to reply
 

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