<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Problems on Arrays and Strings
P1. Is Unique
Step1:  P2. Check Permutation
Step2:  P3. URLify
Step3:  P4. Palindrome Permutation
Step4:  P5. One Away
Step5:  P6. String Compression
Step6:  P7. Rotate Matrix
Step7:  P8. Zero Matrix
<ASSISTANT_TASK:>
Python Code:
# With Hashmap.
# Time Complexity: O(n)
def if_unique(string):
    chr_dict = {}
    for char in string:
        if char not in chr_dict:
            chr_dict[char] = 1
        else:
            return False
    
    return True
# Without additional memory.
# Time Complexity: O(n^2)
def if_unique_m(string):
    for idx, char in enumerate(string):
        for j in range(idx + 1, len(string)):
            if char == string[j]:
                return False
    
    return True
# Test cases.
print(if_unique("1234"), if_unique_m("1234"))
print(if_unique("12344"), if_unique_m("12344"))
print(if_unique("1214"), if_unique_m("1214"))
print(if_unique("1"), if_unique_m("1"))
print(if_unique(""), if_unique_m(""))
Explanation: Problems on Arrays and Strings
P1. Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
End of explanation
# Using a hashmap.
# Checking if str1 is a permutation of str2.
# Assumptions: The strings can have repeated characters.
# Time Complexity: O(n)
def if_permute(str1, str2):
    if len(str1) != len(str2):
        return False
    
    def get_chr_dict(string):
        chr_dict = {}
        for char in string:
            if char not in chr_dict:
                chr_dict[char] = 1
            else:
                chr_dict[char] += 1
        return chr_dict
    
    str1_d = get_chr_dict(str1) # String 1.
    str2_d = get_chr_dict(str2) # String 2.
    
    # Compare dictionaries.
    for char in str1_d:
        if char not in str2_d or str2_d[char] != str1_d[char]:
            return False
    
    return True
# Test Cases
print(if_permute("", ""))
print(if_permute("abc", "abc"))
print(if_permute("abbc", "abbc"))
print(if_permute("abcc", "abcc"))
print(if_permute("aaa", "aaa"))
print(if_permute("aaad", "aaac"))
Explanation: P2. Check Permutation: Given two strings, write a method to decide if one is the permutation of the other.
End of explanation
# Replace spaces with %20 characters.
# Time Complexity: O(n)
def replace_space(string):
    parts = string.split(" ")
    url = ""
    for p in parts:
        if p != "":
            url += p + "%20"
    
    return url[:-3]
print(replace_space("Mr John Smith   "))
print(replace_space(""))
print(replace_space(" John Smith"))
Explanation: P3. 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.
End of explanation
# Build dictionary of all characters in the string and check if all even.
def check_palin_permute(string):
    c_dict = {}
    for char in string:
        if char is not " ":
            if char in c_dict:
                c_dict[char] += 1
            else:
                c_dict[char] = 1
    
    num_1 = 0
    for char in c_dict:
        if c_dict[char]%2 == 1:
            num_1 += 1
    
    if num_1 > 1:
        return False
    return True
print(check_palin_permute("tact coa"))
Explanation: P4. Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palidrome does not need to be limited to just dictionary words.
End of explanation
# Check the length of the strings to find which operation needs to be performed i.e. insert, delete or replace.
# Time Complexity: O(n)
def edit_distance(str1, str2) -> bool:
    if abs(len(str1) - len(str2)) > 1:
        return False
    
    i = 0; j = 0; edits = 0
    while(i < len(str1) and j < len(str2)):
        if str1[i] != str2[j]: # Either replace or move.
            edits += 1
            if len(str1) > len(str2):
                j += 1
            elif len(str1) < len(str2):
                i += 1
                
        i += 1; j += 1
            
    if edits > 1:
        return False
    return True
print(edit_distance("pale", "ple"))
print(edit_distance("pale", "bake"))
print(edit_distance("pales", "pale"))
print(edit_distance("pale", "bale"))
print(edit_distance("pales", "bale"))
Explanation: P5. 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.
End of explanation
# Perform running compression on a string.
# Time Complexity: O(n)
def compress(string: str) -> str:
    com_str = ""
    count = 0
    for i in range(0, len(string) - 1):
        if string[i] == string[i+1]:
            count += 1
        else:
            com_str += string[i] + str(count + 1)
            count = 0 # Reset count.
    
    # Edge case for last character.
    if string[i] == string[i+1]:
        com_str += string[i] + str(count + 1)
    else:
        com_str += string[i+1] + str(1)
    
    if len(com_str) > len(string):
        return string
    
    return com_str
print(compress("aabbbcdefgFFFFFFFFFc"))
print(compress("aabbbcdefgFFFFFFFFF"))
print(compress("aabbbcdefgFFFF"))
Explanation: P6. String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string "aabcccccaaa" would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a-z)
End of explanation
# Rotate a Matrix in-place.
# Given: The matrix is a square matrix.
# Time Complexity: O(n^2)
# Space Complexity: n^2
Matrix = List[List[int]]
def rotate_matrix(mat: Matrix) -> Matrix:
    mat_size = (len(mat), len(mat[0]))
    
    # Create Matrix of equal size.
    rot = [[] for i in range(0 , mat_size[0])]
    for i in range(mat_size[0] - 1, -1, -1):
        for j in range(0, mat_size[1]):
            rot[j].append(mat[i][j])
            
    return rot
rotate_matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]])
# print(swap(2, 3))
Explanation: P7. Rotate Matrix: Given an image represented by an NxN matrix, where each pixel in the imgae is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
End of explanation
# NOTE: This problem is flawed because by making an entire row and column 0, the entire matrix will become zero.
# Make a zero matrix from a given matrix.
# Time complexity: O(n^3)
Matrix = List[List[int]]
def zero_matrix(mat: Matrix) -> Matrix:
    zero_c = {}
    zero_r = {}
    mat_size = (len(mat), len(mat[0]))
    for i in range(0, mat_size[0]):
        for j in range(0, mat_size[1]):
            if mat[i][j] == 0 and i not in zero_r and j not in zero_c:
                for k in range(0, mat_size[0]):
                    mat[k][j] = 0
                for k in range(0, mat_size[1]):
                    mat[i][k] = 0
                
                zero_r[k] = 1
                zero_c[k] = 1
    
    return mat
print(zero_matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]]))
Explanation: P8. Zero Matrix: Write an algorithm such that if an element in an NxN matrix is 0, its entire row and column are set to 0.
End of explanation
<END_TASK>