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

  • 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"