Simple solution in Java


  • 29

    We start from i = 1 and check whether current and previous characters of the input string equals to +. If true, then add substring to a list: characters before previous one (concatenating with --) and characters after the current character.

    public List<String> generatePossibleNextMoves(String s) {
        List<String> list = new ArrayList<String>();
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '+' && s.charAt(i - 1) == '+') {
                list.add(s.substring(0, i - 1) + "--" + s.substring(i + 1, s.length()));
            }
        }
        return list;
    }

  • 2
    D

    Out of curiosity, why do you do:

    for (int i = 1; i < s.length(); i++)

    instead of

    for (int i = 0; i < s.length() - 1; i++)

    I realize it's just semantics, but it seems clearer and more common to start at 0 and check the next space in these kinds of problems.


  • 0
    This post is deleted!

  • -3
    W
    This post is deleted!

  • 0
    X

    because the first pair may appear when i=1, not i=0.


  • 0
    J

    No, it's simply a matter of semantics. You just have to modify how much to append when substringing.


  • 0
    G

    Hi @IDreaml what is the time complexity of your solution ? It looks N-squared to me.


  • 0
    A
    This post is deleted!

  • 1

    @GreenTea211

    One pass. It's O(n)


  • 0

    Yeah, you are right.

    public List<String> generatePossibleNextMoves(String s) {
    	List<String> rst=new ArrayList<>();
    	for(int i=0;i<s.length()-1;i++){
             if(s.charAt(i)=='+' && s.charAt(i+1)=='+'){
              rst.add(s.substring(0,i)+"--"+s.substring(i+2,s.length()));
    	}
        }
        return rst;
    }

  • 0
    M

    Nice solution.
    The line

    if (s.charAt(i) == '+' && s.charAt(i - 1) == '+')
    

    can be simplified as

    if (s.startsWith("++", i))
    

    So the simplified code using your idea is

    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.startsWith("++", i)) {
                result.add(s.substring(0, i) + "--" + s.substring(i + 2));
            }
        }
        return result;
    }
    

Log in to reply
 

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