[알고리즘] 코딩인터뷰 완전분석 - 1.5 하나 빼기

1.5 하나 빼기

문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체, 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라.

• unordered_set 을 사용하는 경우 - O(n)

  #include <iostream>
  #include <unordered_set>
  #include <string>
  
  using namespace std;
  
  bool solution(string str1, string str2) {
      unordered_set<char> s;
      size_t len1 = str1.length();
      size_t len2 = str2.length();
  
      if (len1 > len2) {
          for (char &c : str1) 
              s.insert(c);
  
          for (char &c : str2) {
              if (s.find(c) != s.end()) 
                  s.erase(c);
              else 
                  s.insert(c);
          }
      }
      else {
          for (char &c : str2)
              s.insert(c);
  
          for (char &c : str1) {
              if (s.find(c) != s.end())
                  s.erase(c);
              else
                  s.insert(c);
          }
      }
  
      if (s.size() <= 2)
          return true;
      else
          return false;
  }
  
  int main()
  {
      string str1 = "bake", str2 = "pale";
      bool res;
  
      res = solution(str1, str2);
      cout << boolalpha << res << endl; 
  }

• hash_set 을 이용했다. 입력 값으로 들어온 두 문자열의 길이를 비교한 뒤 로직을 수행한다.

• 만일 str1 이 str2 보다 문자열 길이가 긴 경우(str1 : pales, str2 : pale), str1 의 각 문자를 set 에 넣는다. 그리고 str2 의 각 문자를 검사한다. str2 에서 뺀 문자가 set 에 이미 있다면 지우고, 없으면 set 에 추가한다.

• str1의 길이 < str2의 길이 인 경우도 마찬가지다.

• 마지막에 if (s.size() <= 2) 를 통해 편집 여부를 확인한다. 만일 set 의 크기가 2 이하인 경우는 true, 2보다 클 경우는 false를 리턴한다.

    str1         str2         set.size()
   "pale"       "ple"              1
   "pales"      "pale"             1
   "pale"       "bale"             2
   "pale"       "bake"             4

---

• 교재 풀이 - O(n)

  bool one_edit_away(string first, string second) {
      if (first.length() == second.length()) {
          return one_edit_replace(first, second);
      } else if (first.length() + 1 == second.length()) {
          return one_edit_insert(first, second);
      } else if (first.length() - 1 == second.length()) {
          return one_edit_insert(second, first);
      }
  }
  
  bool one_edit_replace(string s1, string s2) {
      bool found_difference = false;
  
      for (int i = 0; i < s1.length(); i++) {
          if (s1.at(i) != s2.at(i)) {
              if (found_difference) {
                  return false;
              }
              found_difference = true;
          }
      }
      return true;
  }
  
  bool one_edit_insert(string s1, string s2) {
      int idx1 = 0;
      int idx2 = 0;
  
      while (idx2 < s2.length() && idx1 < s1.length()) {
          if (s1.at(idx1) != s2.at(idx2)) {
              if (idx1 != idx2) {
                  return false;
              }
              idx2++;
          } else {
              idx1++;
              idx2++;
          }
      }
  
      return true;
  }

  • one_edit_replace 함수에서 이전 포스팅에서 언급한 기법?을 또 사용하고 있다. (중복 찾을 때의 소스코드와 유사함) 여기서도 found_difference 변수를 가지고 다른 문자가 1개 이상인 것을 체크한다.
  • one_edit_insert 함수에서 주목해야 할 것을 while문이다. 같은 문자가 아닐 때 넘기는 로직이 간단하다.