The Self-Taught Computer Scientist
Introduction to Algorithms
Download 1.48 Mb. Pdf ko'rish
|
books-library.net-11301817Az7X6
- Bu sahifa navigatsiya:
- Chapter 5
Introduction to Algorithms
56 Anagrams sometimes contain multiple words and include uppercase and lowercase letters, so you start your function by removing spaces from your strings and converting all the characters to lowercase: s1 = s1.replace(' ','').lower() s2 = s2.replace(' ','').lower() You then sort both strings and compare the result to determine whether they are the same. If they are, the strings are anagrams, and you return True . Otherwise, they are not, and you return False . if sorted(s1) == sorted(s2): return True else: return False Because your algorithm to detect anagrams relies on Python’s built- in sorted function, its run time is O( n log n). Palindrome Detection A palindrome is a word that reads the same backward as forward. Hannah, mom, wow, and racecar are all examples of palindromes. There are several ways to determine whether a string is a palindrome. One way is to copy the string, reverse it, and compare it to the original. If they are equal, the string is a palindrome. Here is how to reverse a string in Python: print("blackswan"[::- 1]) >> nawskcalb Here is how to check whether a string is a palindrome: def is_palindrome(s1): if s1.lower() == s1[::- 1].lower(): return True return False First, you use Python’s built- in lower function to make sure capitalization doesn’t affect your comparison. Then, you use Python’s slicing syntax to reverse the string and compare it to the original: if s1.lower() == s1[::- 1].lower(): If the two strings are the same, the string is a palindrome, and you return True : return True Chapter 5 String Algorithms 57 Otherwise, the strings are not palindromes, and you return False : Return False The slowest part of your algorithm to detect palindromes is Python’s syntax for reversing a list. Because Python has to visit every item in a list to reverse it, the run time to reverse a list is O( n), which makes your algorithm’s run time O( n) as well. Last Digit Another common interview question is to return the rightmost digit in a string. For example, given the string "Buy 1 get 2 free" , your function should return the number 2. One elegant way to solve this problem is to use Python’s list comprehension feature. A list com- Download 1.48 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling