Python의 화이트보드: 문자열이 회문의 배열인지 확인

| | View Solution on GitHub

네가 위에서 본 것은 멕시코 옥수수말이 고양이의 맞춤법이 거꾸로 되었다.(출처: popsugar.com)
우리는 이번 주에 다시 돌아와서 또 다른 연습 문제를 가져왔다.이번에는 더 간단한 수조와 문자열이나, 우리가Python에서 목록과 문자열이라고 부른다.이 문제를 살펴보겠습니다.

# Given a string, write a function to check if it is a permutation of a palindrome. 
# A palindrome does not to be limited to just dictionary words. 
# You can ignore casing and non-letter characters.

우리가 있는 이곳에는 몇 개의 유행어가 있는데, 그들은 이런 문제에서 사용하는 것을 좋아한다.네가 알 수 있는 회문은 앞뒤로 같은 내용을 읽고 있는 단어, 예를 들면'멕시코 롤케이크 고양이'다.공백이 어떻게 무시되는지 주의하십시오. 이 문제 역시 비자모 문자를 무시해야 할 것 같습니다.배열은 바로 자모의 어떤 재배열이다.예를 들어 우리는 문자열 "tacocat"의 알파벳 순서를 "aaccott"로 정렬할 수 있습니다. 이것은 "tacocate"의 배열입니다. (이 해결 방안을 위해 문자열을 정렬하지는 않겠지만, 이 생각을 기억하는 것이 가장 좋습니다.
정의 방법부터 시작합시다.너는 Repl에서 스스로 따라갈 수 있다.아니면 전통적인 방식으로 그것을 백판과 종이에 쓴 다음에 그것을 꺼내서 완성한 후에 운행해 보세요.어쨌든 스스로 해 보는 것이 좋겠다.

def check_pali(our_string):
    pass

먼저 프롬프트의 세부 문자는 "케이스 무시"를 나타냅니다.할 수 있다문자열 .lower() 을 호출합시다. our_string 로 정의하기 쉽습니다..lower() 소문자 문자열을 반환하고 원래 문자열을 변경하지 않으므로 our_string 에 다시 저장해야 합니다.

def check_pali(our_string):
    our_string = our_string.lower()

우리들은 우리의 방법을 생각해 봅시다.모든 회문에는 어떤 공통 속성이 있습니까?Tacocate,racecar,kayak 등의 예시를 보면 알파벳마다 중간 알파벳을 제외하고 두 번씩 나타나는 것을 알 수 있습니다.비교적 긴 회문에서, 예를 들면 "거위가 하느님을 보았습니까?"일부 알파벳은 두 번 이상 나타날 수 있지만 ('e'는 네 번 나타날 수 있지만, 최대 한 알파벳은 홀수 횟수가 나타날 수 있다.따라서 만약에 우리가 모든 알파벳의 출현 횟수를 계산한다면 모든 알파벳의 출현 횟수는 반드시 짝수, 최대 하나의 홀수이어야 한다.
우리는 모든 알파벳의 계수를 저장하기 위해 데이터 구조를 만들 것이다.코딩 면접을 풀 수 있는 해결 방안이 해시표를 실현했다.해시표가 뭐냐고요?어디 보자Wikipedia page for Hash Tables:

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.

키 및 값?만약 그것이 파이썬 사전처럼 들린다면, 너는 옳다. 왜냐하면 이것이 우리가 사용해야 하기 때문이다.
우리는 사전 counts 을 빈 사전으로 초기화합니다.

def check_pali(our_string):
  our_string = our_string.lower()
  counts = {}

다음은 문자열을 훑어보도록 하겠습니다.우리는 각 캐릭터를 통해 순환하는 for 순환을 만들 것이다.

for letter in our_string:

현재, 우리는 알파벳 문자만 계산할 것을 확보해야 한다. 왜냐하면 비자모는 무시되기 때문이다.가장 간단한 galaxy brain 방법은 알파벳표의 모든 알파벳으로 문자열을 쓰고 문자가 포함되어 있는지 확인하는 것이다.

if letter in "abcdefghijklmnopqrstuvwxyz":

그러나 또 다른 방법은 사용법ord()으로 주어진 문자의 유니코드 값을 되돌려 면접관에게 깊은 인상을 남길 수 있다."a"와 "z"의 값을 찾거나 print(ord('a')) 와 print(ord('z')) 를 사용하여python 컨트롤러에서 출력할 수 있습니다.유니코드에서 대문자 값이 첫 번째이기 때문에 소문자인지 확인하십시오.이 값을 사용하면 조건은 다음과 같습니다.

if ord(letter) >= 97 and ord(letter) <= 122:

이제 자모 계수로 사전을 채워 봅시다.전통적인 지혜는 하나의 조건을 세우는 것이다. 만약 이 키가 존재하지 않는다면, 우리는 그것을 1로 초기화하고, 만약 그것이 존재한다면, 우리는 그것에 하나를 추가할 것이다.이것은 우리가 존재하지 않는 키에 접근하려는 값의 오류를 없앴다.그것은 보기에 이렇다.

counts = {}
for letter in our_string:
    if letter in counts.keys():
      counts[letter] += 1
    elif ord(letter) >= 97 and ord(letter) <= 122:
      counts[letter] = 1 

이거 좋아요.이를 더욱 간소화하려면 파이썬에 defaultdict 이라는 내장 클래스가 있습니다. 이 클래스의 값은 자동으로 정수로 가정할 수 있습니다. 이것은 새 키를 처음 호출하면 값이 0으로 초기화된다는 것을 의미합니다.그리고 사전의 키든 아니든 모든 값을 하나만 늘리면 됩니다.이 방법을 사용하면 가져오기가 파일의 맨 위에 포함되어 있는지 확인합니다.

from collections import defaultdict

counts = defaultdict(int)
for letter in our_string:
    if ord(letter) >= 97 and ord(letter) <= 122:
      counts[letter] += 1 

멋있어, 그래서 지금 우리는 자모 하나하나의 계수가 있는 사전이 있어야 해.만약 우리가 "Tacocat"과 같은 함수를 실행한 후에 사전을 인쇄한다면, 우리는 다음과 같은 결과를 얻어야 한다.

{'t': 2, 'a': 2, 'c': 2, 'o': 1}

대소문자와 공백을 무시하는 방법을 주의하십시오.
다음으로, 우리는 사전의 모든 알파벳을 훑어보고, 모든 값이 짝수, 최대 홀수인지 확인해야 한다.python for 순환은 사전의 모든 키를 제공하기 때문에 변수 letter 로 저장합니다.

for letter in counts:

현재 우리는 변수를 만들어서 홀수를 찾았는지 저장하려고 합니다.변수 middle 로 저장할 수 있으며, 홀수를 보면 중간 문자로 저장할 수 있습니다.변수를 True 또는 False로 간단히 설정할 수도 있습니다.그리고 계수가 홀수인지 짝수인지 확인하기 위해서 우리는 모형 연산자를 사용하는데, 이것은 나눗셈 후의 나머지를 되돌려준다.% 2 값이 홀수이면 항상 1을 반환하고 짝수이면 항상 0을 반환합니다.만약 홀수가 있고 중간에 "truthy"값이 있다면, 우리는 False로 돌아가야 한다.총:

middle = ""
for letter in counts:
    if middle and counts[letter] % 2 == 1:
        return False
    elif counts[letter] % 2 == 1:
        middle = letter

마지막으로, 만약 우리가 목록을 두루 훑어보았고 모든 내용이 서명되었다면, 반드시 True로 돌아가야 한다.따라서 문장return True은 뛰쳐나와for 순환한다.마지막 방법은 다음과 같습니다.
회문 배열.회사 명

def check_pali(our_string):
  our_string = our_string.lower()
  counts = defaultdict(int)
  for letter in our_string:
    if ord(letter) >= 97 and ord(letter) <= 122:
      counts[letter] += 1 
  # print(counts)
  middle = ""
  for letter in counts:
    if middle and counts[letter] % 2 == 1:
      return False
    elif counts[letter] % 2 == 1:
      middle = letter
  return True

만약 우리가 회문, 예를 들어'멕시코 옥수수말이 고양이'를 실행하려고 한다면, 이 방법은 트루로 돌아가야 하고,'회문이 아닌 것'은 False로 돌아가야 한다.

print(check_pali("Taco cat"))
-> True
print(check_pali("Not a palindrome"))
-> False

이렇게우리의 해결 방안의 시간 복잡도는 O(N)입니다. 왜냐하면 우리는 목록에 있는 모든 항목을 최소한 한 번 순환해야 하기 때문입니다.

보상: 가능한 답장 반환

이것은 내가 이 문제를 위해 제기한 추가적인 특성이다.만약 우리에게 알파벳 문자열을 주었다면, 우리는 그것이 회문의 배열인지 알고 싶을 뿐만 아니라, 만약 그렇다면, 회문은 어떤 모습일까?
중간 문자부터 우리는 그것을 새 회문의 중간 부분으로 삼는다.그런데 한 번이 아니라면?우리는 반드시 그것을 그 계수에 곱해야 한다.파이썬은 문자열 곱셈을 통해 이 과정을 간소화했고, 그 중에서 'a' * 3 은 'aaa' 되돌아왔다.

new_pali = ""
if middle:
    new_pali = middle * counts[middle]

다음에 우리는 사전을 반복해서 계수의 절반을 중간 문자의 한쪽에 추가합니다.나눗셈은 10진수를 되돌려주는데, 부동점이라고도 부른다.따라서 문자열 곱셈을 할 수 있도록 int로 다시 변환해야 합니다. True로 되돌아온 줄을 주석해야 합니다.

  new_pali = ""
  if middle:
    new_pali = middle * counts[middle]
  for letter in counts:
    if letter != middle:
      new_pali = letter * int(counts[letter] / 2) + new_pali + letter * int(counts[letter] / 2) 
  return new_pali

"Taco cat"인쇄 결과는 "catotac"으로 돌아갑니다.깔끔했어만약 네가 어떤 단어를 두 번 전입한다면, 그것은 회문이 될 것이다.예를 들어 "word word"는 "drowword"를 되돌려줍니다.나는 이런 방법이 너의 일생에서 잃어버린 일이라는 것을 안다.천만에요.
이번 주에 들어주셔서 감사합니다.우리는 다음 주 월요일에 돌아와서 알고리즘을 배우기 시작할 것이다.그때 봐요!
| | View Solution on GitHub
Sheamus Heikkila는 예전에 시애틀 대회의 조교였다.이 블로그는 GA와 무관합니다.