Java 3ms O(n) solution


  • 0
    P

    public class Solution {
    public boolean wordPattern(String pattern, String str) {
    if (pattern == null) {
    return false;
    }
    String[] strs = str.split(" ");
    if (pattern.length() != strs.length) {
    return false;
    }
    HashSet<String> added = new HashSet<String>();
    HashMap<Character, String> map = new HashMap<Character, String>();
    for (int i = 0; i< strs.length; i++) {
    if (map.containsKey(pattern.charAt(i))) {
    if (!map.get(pattern.charAt(i)).equals(strs[i])) {
    return false;
    }
    } else {
    if (added.contains(strs[i])) {
    return false;
    } else {
    added.add(strs[i]);
    }
    map.put(pattern.charAt(i), strs[i]);
    }
    }
    return true;
    }
    }


  • 0
    N

    Time complexity is O(n*m) where n is number of entries in string array and m is size of string.


  • 0
    K

    @neo we could treat size of a string is bounded by a constant m. f(n) <= mn = O(n). Refer to http://web.mit.edu/16.070/www/lecture/big_o.pdf


  • 0
    N

    @kotomi_null the only time you can say m is constant if its not going to vary irrespective of the size of n, which is not the case here. Think about it. If you still think its the same good luck.


  • 0
    K

    "bounded by a constant m"... Big O annotation


Log in to reply
 

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