演算法練習筆記

1. 注意題目裡的線索
   例如題目如果出現”寫一個在伺服器長時間重複運作的程式”，你可以想看看快取是不是可以派上用場

2. 寫出測試範例
   要特別注意自己寫出來的範例是不是特例

3. 嘗試暴力解

4. 優化

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other. p.90

def check_permutation(s1, s2):
    if len(s1) != len(s2):
        return False
    sd1 = {}
    for i in s1:
        if sd1.get(i):
            sd1[i] = sd1[i] + 1
        else:
            sd1[i] = 1
    for j in s2:
        if sd1.get(j):
            if sd1.get(j) > 0:
                sd1[i] = sd1[i] - 1
            else:
                return False
        else:
            return False
    return True
        

samples

• dad, bda
• abc, bca
• sss, sss
• sas, ssa
• abcd, abc
• bbba, bbbb

URLify: Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the “true” length of the string. (Note: If implementing in Java, please use a character array so that you can perform this operation in place.)

• 錯誤1:
  忘記回傳值

Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palin-drome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

import copy

def palindrome(input):
    input = input.lower()
    char_dict = {}
    for c in input:
        if c != " ":
            if char_dict.get(c):
                char_dict.pop(c)
            else:
                char_dict[c] = 1
    if len(char_dict) > 1:
        return False
    return True

錯誤1: 沒有考慮到大小寫問題

One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

def one_edit(str_a, str_b):
    if len(str_a) - len(str_b) == -1:
        for c in str_a:
            if c not in str_b:
                return False
    elif len(str_a) - len(str_b) == 1:
        for c in str_b:
            if c not in str_a:
                return False
    elif len(str_a) - len(str_b) == 0:
        counter = 0
        for c in str_a:
            if c not in str_b:
                counter +=1
        if counter > 1:
            return False
    else:
        return False
    return True