Skip to content

Commit 7cbe6e1

Browse files
Hai Hoang Danggoswami-rahul
Hai Hoang Dang
authored and
goswami-rahul
committed
Added some String algorithm (keon#356)
* Add unique morse * Add judge_circle * Add strong password
1 parent 18b9ce1 commit 7cbe6e1

6 files changed

Lines changed: 189 additions & 2 deletions

File tree

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -284,6 +284,9 @@ If you want to uninstall algorithms, it is as simple as:
284284
- [reverse_words](algorithms/strings/reverse_words.py)
285285
- [roman_to_int](algorithms/strings/roman_to_int.py)
286286
- [word_squares](algorithms/strings/word_squares.py)
287+
- [unique_morse](algorithms/strings/unique_morse.py)
288+
- [judge_circle](algorithms/strings/judge_circle.py)
289+
- [strong_password](algorithms/strings/strong_password.py)
287290
- [tree](algorithms/tree)
288291
- [bst](algorithms/tree/tree/bst)
289292
- [array2bst](algorithms/tree/bst/array2bst.py)

‎algorithms/strings/__init__.py‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,3 +21,6 @@
2121
from .strip_url_params import *
2222
from .validate_coordinates import *
2323
from .word_squares import *
24+
from .unique_morse import *
25+
from .judge_circle import *
26+
from .strong_password import *

‎algorithms/strings/judge_circle.py‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
"""
2+
Initially, there is a Robot at position (0, 0). Given a sequence of its moves,
3+
judge if this robot makes a circle, which means it moves back to the original place.
4+
5+
The move sequence is represented by a string. And each move is represent by a
6+
character. The valid robot moves are R (Right), L (Left), U (Up) and D (down).
7+
The output should be true or false representing whether the robot makes a circle.
8+
9+
Example 1:
10+
Input: "UD"
11+
Output: true
12+
Example 2:
13+
Input: "LL"
14+
Output: false
15+
"""
16+
def judge_circle(moves):
17+
dict_moves = {
18+
'U' : 0,
19+
'D' : 0,
20+
'R' : 0,
21+
'L' : 0
22+
}
23+
for char in moves:
24+
dict_moves[char] = dict_moves[char] + 1
25+
return dict_moves['L'] == dict_moves['R'] and dict_moves['U'] == dict_moves['D']

‎algorithms/strings/strong_password.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
"""
2+
The signup page required her to input a name and a password. However, the password
3+
must be strong. The website considers a password to be strong if it satisfies the following criteria:
4+
5+
1) Its length is at least 6.
6+
2) It contains at least one digit.
7+
3) It contains at least one lowercase English character.
8+
4) It contains at least one uppercase English character.
9+
5) It contains at least one special character. The special characters are: !@#$%^&*()-+
10+
She typed a random string of length in the password field but wasn't sure if it was strong.
11+
Given the string she typed, can you find the minimum number of characters she must add to make her password strong?
12+
13+
Note: Here's the set of types of characters in a form you can paste in your solution:
14+
numbers = "0123456789"
15+
lower_case = "abcdefghijklmnopqrstuvwxyz"
16+
upper_case = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
17+
special_characters = "!@#$%^&*()-+"
18+
19+
Input Format
20+
The first line contains an integer denoting the length of the string.
21+
The second line contains a string consisting of characters, the password
22+
typed by Louise. Each character is either a lowercase/uppercase English alphabet, a digit, or a special character.
23+
24+
Sample Input 1: strong_password(3,"Ab1")
25+
Output: 3 (Because She can make the password strong by adding characters,for example, $hk, turning the password into Ab1$hk which is strong.
26+
2 characters aren't enough since the length must be at least 6.)
27+
28+
Sample Output 2: strong_password(11,"#Algorithms")
29+
Output: 1 (Because the password isn't strong, but she can make it strong by adding a single digit.)
30+
31+
"""
32+
def strong_password(n, password):
33+
count_error = 0
34+
# Return the minimum number of characters to make the password strong
35+
if any(i.isdigit() for i in password) == False:
36+
count_error = count_error + 1
37+
if any(i.islower() for i in password) == False:
38+
count_error = count_error + 1
39+
if any(i.isupper() for i in password) == False:
40+
count_error = count_error + 1
41+
if any(i in '!@#$%^&*()-+' for i in password) == False:
42+
count_error = count_error + 1
43+
return max(count_error, 6 - n)

‎algorithms/strings/unique_morse.py‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
"""
2+
International Morse Code defines a standard encoding where each letter is mapped to
3+
a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c"
4+
maps to "-.-.", and so on.
5+
6+
For convenience, the full table for the 26 letters of the English alphabet is given below:
7+
'a':".-",
8+
'b':"-...",
9+
'c':"-.-.",
10+
'd': "-..",
11+
'e':".",
12+
'f':"..-.",
13+
'g':"--.",
14+
'h':"....",
15+
'i':"..",
16+
'j':".---",
17+
'k':"-.-",
18+
'l':".-..",
19+
'm':"--",
20+
'n':"-.",
21+
'o':"---",
22+
'p':".--.",
23+
'q':"--.-",
24+
'r':".-.",
25+
's':"...",
26+
't':"-",
27+
'u':"..-",
28+
'v':"...-",
29+
'w':".--",
30+
'x':"-..-",
31+
'y':"-.--",
32+
'z':"--.."
33+
34+
Now, given a list of words, each word can be written as a concatenation of the
35+
Morse code of each letter. For example, "cab" can be written as "-.-.-....-",
36+
(which is the concatenation "-.-." + "-..." + ".-"). We'll call such a
37+
concatenation, the transformation of a word.
38+
39+
Return the number of different transformations among all words we have.
40+
Example:
41+
Input: words = ["gin", "zen", "gig", "msg"]
42+
Output: 2
43+
Explanation:
44+
The transformation of each word is:
45+
"gin" -> "--...-."
46+
"zen" -> "--...-."
47+
"gig" -> "--...--."
48+
"msg" -> "--...--."
49+
50+
There are 2 different transformations, "--...-." and "--...--.".
51+
"""
52+
53+
morse_code = {
54+
'a':".-",
55+
'b':"-...",
56+
'c':"-.-.",
57+
'd': "-..",
58+
'e':".",
59+
'f':"..-.",
60+
'g':"--.",
61+
'h':"....",
62+
'i':"..",
63+
'j':".---",
64+
'k':"-.-",
65+
'l':".-..",
66+
'm':"--",
67+
'n':"-.",
68+
'o':"---",
69+
'p':".--.",
70+
'q':"--.-",
71+
'r':".-.",
72+
's':"...",
73+
't':"-",
74+
'u':"..-",
75+
'v':"...-",
76+
'w':".--",
77+
'x':"-..-",
78+
'y':"-.--",
79+
'z':"--.."
80+
}
81+
def convert_morse_word(word):
82+
morse_word = ""
83+
word = word.lower()
84+
for char in word:
85+
morse_word = morse_word + morse_code[char]
86+
return morse_word
87+
88+
def unique_morse(words):
89+
unique_morse_word = []
90+
for word in words:
91+
morse_word = convert_morse_word(word)
92+
if morse_word not in unique_morse_word:
93+
unique_morse_word.append(morse_word)
94+
return len(unique_morse_word)

‎tests/test_strings.py‎

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,10 @@
2323
strip_url_params1, strip_url_params2, strip_url_params3,
2424
is_valid_coordinates_0, is_valid_coordinates_1,
2525
is_valid_coordinates_regular_expression,
26-
word_squares
26+
word_squares,
27+
convert_morse_word, unique_morse,
28+
judge_circle,
29+
strong_password
2730
)
2831

2932
import unittest
@@ -291,7 +294,7 @@ def test_pythonic(self):
291294
self.assertEqual("ereht olleh", pythonic("hello there"))
292295
def test_ultra_pythonic(self):
293296
self.assertEqual("ereht olleh", ultra_pythonic("hello there"))
294-
297+
295298

296299
class TestReverseVowel(unittest.TestCase):
297300
"""[summary]
@@ -381,6 +384,22 @@ def test_word_squares(self):
381384
self.assertEqual([['wall', 'area', 'lead', 'lady'], ['ball', 'area', 'lead', 'lady']], \
382385
word_squares(["area","lead","wall","lady","ball"]))
383386

387+
class TestUniqueMorse(unittest.TestCase):
388+
def test_convert_morse_word(self):
389+
self.assertEqual("--...-.", convert_morse_word("gin"))
390+
self.assertEqual("--...--.", convert_morse_word("msg"))
391+
def test_unique_morse(self):
392+
self.assertEqual(2, unique_morse(["gin", "zen", "gig", "msg"]))
393+
394+
class TestJudgeCircle(unittest.TestCase):
395+
def test_judge_circle(self):
396+
self.assertTrue(judge_circle("UDLRUD"))
397+
self.assertFalse(judge_circle("LLRU"))
398+
399+
class TestStrongPassword(unittest.TestCase):
400+
def test_strong_password(self):
401+
self.assertEqual(3, strong_password(3,"Ab1"))
402+
self.assertEqual(1, strong_password(11,"#Algorithms"))
384403

385404
if __name__ == "__main__":
386405
unittest.main()

0 commit comments

Comments
 (0)