11ms Java O(n) ransomNote minimal


  • 0
    T
    public class Solution {
    
        public boolean canConstruct(String ransomNote, String magazine) {
            char[] notes = ransomNote.toCharArray();
            int index;
            for (int i = 0; i < notes.length; i++) {
                if (notes[i] == '.')
                    continue;
                else if ((index = magazine.indexOf(notes[i])) < 0)
                    return false;
                else {
                    int j = i;
                    while ((j = ransomNote.indexOf(notes[i], j + 1)) >= 0) {
                        if ((index = magazine.indexOf(notes[i], index + 1)) < 0)
                            return false;
                        notes[j] = '.';
                    }
                }
            }
            return true;
        }
    }
    

  • 0
    G

    This solution should be O(n^2) time cause the use of indexOf is indeed a for loop.


Log in to reply
 

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