Created
January 26, 2024 18:03
-
-
Save jgs03177/2a153394e627f8e82a79cb908cf55385 to your computer and use it in GitHub Desktop.
울라리
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def generate_shortname(s): | |
| """generate all the possible short name of s | |
| where the output should be a subsequence of s containing the first letter of s. | |
| s : original name (string) | |
| """ | |
| assert len(s)>=2, "The length of the string should be at least 2." | |
| t0, *t = s | |
| len_t = len(t) | |
| oo = [] | |
| for b in range(1<<len_t): # all possible positions as a bit format | |
| o = [t0] | |
| for i in range(len(t)): | |
| if b&1: | |
| o+=[t[i]] | |
| b>>=1 | |
| oo += [''.join(o)] | |
| oo = list(set(oo)) # remove duplicates | |
| oo.sort(key=lambda x: (len(x), x)) | |
| return oo[1:-1] # exclude length 1 and length len(s) | |
| def check_shortname(s,t): | |
| """check if t is a short name of s. | |
| s: original name | |
| t: short name candidate | |
| """ | |
| if len(t) == 0 or len(t) > len(s): | |
| return False # string is too short or long to check | |
| if len(t) == 1 or len(t) == len(s): | |
| return False # exclude length 1 or length s | |
| check_initial = s[0]==t[0] | |
| if not check_initial: | |
| return False | |
| i=1 | |
| j=1 | |
| len_s = len(s) | |
| len_t = len(t) | |
| # greedy two pointer matching | |
| while i<len_s and j<len_t: | |
| c=t[j] | |
| if s[i]==c: | |
| j+=1 | |
| i+=1 | |
| if j!=len_t: | |
| return False | |
| return True | |
| if __name__=="__main__": | |
| all_ulrali = generate_shortname("울트라리스크") | |
| print(*all_ulrali, sep='\n') | |
| bltank_check = check_shortname("blitzcrank", "bltank") | |
| print(bltank_check) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment