We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Abbreviation
  5. Discussions

Abbreviation

Sort by

recency

|

610 Discussions

|

  • Tusenka
     + 0 comments

    def _check(a, b): print(a, b) dp=[[ False for _ in range(len(a)+1) ] for _ in range(len(b)+1)] dp[0][0]=True for j in range(1, len(a)+1): if a[j-1].islower() and dp[0][j-1]: dp[0][j]=True else: break for i in range(1, len(b)+1): for j in range(1, len(a)+1): if a[j-1]==b[i-1]: dp[i][j]=dp[i-1][j-1] elif a[j-1].upper()==b[i-1]: dp[i][j]=dp[i-1][j-1] or dp[i][j-1] elif a[j-1].islower(): dp[i][j]=dp[i][j-1]

    return dp[-1][-1]

    def _remove_unused(a, b): _set_b=set(b) return "".join(list([x for x in a if x.isupper() or x.upper() in _set_b]))

    def _build_dp(a): _dp = collections.defaultdict(int) for _, x in enumerate(a): _dp[x.upper()]+=1 return _dp

    def _precheck_check_dp(dp_a, dp_b): for x in dp_b: if dp_a[x] < dp_b[x]: return False return True

    def abbreviation(a, b): a=_remove_unused(a, b) if len(a) if not _precheck_check_dp(_build_dp(a),_build_dp(b)): return "NO" if _check(a, b): return "YES" else: return "NO"

  • Tusenka
     + 0 comments

    My version. Last three tests is timeout. Think how to avoid recursion. Thanks to sxb427 idea: 1. daBcdc ABC 2. f(daBcdc, ABC) = f(daBcd, AB) or f(daBcd, ABC) 3. Improvment - preremoved lower symbols from which are not in b * aBcc ABC * f(aBc, AB) or f(daBc, ABC) => f(aBc, ABC) => True

    import collections

def _check(a, b):
    if len(a)==1:
        if len(b)==0:
            return a[0].islower()
        else:    
            return a[0].upper()==b[0]
    if a[-1]==b[-1]:
        return _check(a[:-1], b[:-1])
    elif a[-1].upper()==b[-1]:
        return _check(a[:-1], b) or _check(a[:-1], b[:-1]) 
    else:
        return a[-1].islower() and _check(a[:-1], b)
   
def _upper(s, i):
    return s[0:i]+s[i].upper()+s[i+1]


def _remove_unused(a, b):
    _set_b=set(b)
    return "".join(list([x for x in a if x.isupper() or x.upper() in _set_b]))
    

def _build_dp(a):
    _dp = collections.defaultdict(int)
    for _, x in enumerate(a):
       _dp[x.upper()]+=1
    return _dp

def _precheck_check_dp(dp_a, dp_b):
    for x in dp_b:
        if dp_a[x] < dp_b[x]:
            return False
    return True


def abbreviation(a, b):
    a=_remove_unused(a, b)
    if len(a)<len(b):
        return "NO"        
    if not _precheck_check_dp(_build_dp(a),_build_dp(b)):
        return "NO"
    if _check(a, b):
        return "YES"
    else:
        return "NO"

  • Parmera
     + 4 comments

    Trying crazy things to solve it in O(NlogN) My code failed in 3 tests, but i can't think of an small test which it fails, can someone help?

    string abbreviation(string a, string b) {
    int j = 0;
    map<char, int> dp1, dp2;
    for(int i = 0;i<a.size();i++)
    {
        dp1[a[i]]++;
    }
    
    for(int i = 0;i<b.size();i++)
    {
        dp2[b[i]]++;
    }
    
    for(int i = 0;i<b.size();i++)
    {
        dp1[b[i]]--;
        if(dp1[b[i]] < 0)
        {
            dp1[char(b[i]+32)]--;
            if(dp1[char(b[i]+32)] < 0)
                return "NO";
        }
    }
    
    for(int i = 0;i<b.size();i++)
    {
        if(dp1[b[i]]>0)
            return "NO";
    }
    
    for(int i = 0;i<a.size();i++)
    {
        if(dp1[a[i]]>0 && a[i]<='Z')
            return "NO";
    }
    
    for(int i = 0;i<a.size();i++)
    {
        if(a[i] <= 'Z' && dp2.find(a[i]) == dp2.end())
            return "NO";
    }
    
    for(int i = 0;i<a.size();i++)
    {
        if(j < b.size())
        {
            if(a[i] == b[j] || char(a[i]-32) == b[j])
            {
                j++;
            }
        }
    }
    
    if(j == b.size())
    {
        return "YES";
    }
    return "NO";
}

  • anthonyabunassar
     + 1 comment

    I've passed, so this is a moot point, but doesn't the problem statement say you can "delete all of the remaining lowercase letters in a"? This implies that if you start deleting, you have to keep deleting: "all", not "some". Yet this test case does not fail as it should:

    {"abCd", "Cd", false},

  • arssonist
     + 1 comment

    Anyone have a non-code description of how to do this ? Nothing I've tried has worked.