[알고리즘] 문자열 비교

문자열 비교

https://www.careercup.com/question?id=4793416529477632

github

문제 내용

1. 두 문자열을 비교한다.
2. 문자 하나 차이로 증가/삭제/대치를 구분한다.

3. 하나 정도 차이는 같음(true)로 이 이상은 다름(false)로 처리한다.

   /**

   • Implement a function OneEditApart with the following signature:
   • bool OneEditApart(string s1, string s2)
   • OneEditApart("cat", "dog") = false
   • OneEditApart("cat", "cats") = true
   • OneEditApart("cat", "cut") = true
   • OneEditApart("cat", "cast") = true
   • OneEditApart("cat", "at") = true
   • OneEditApart("cat", "acts") = false
   • Edit is: insertion, removal, replacement */

snippet

2이상 차이 경우

2개 이상은 잘 못된것으로 바로 false 처리

if (big_len - small_len > 1)
{
        return false;
}

같은 경우

1개 이상 다른 경우

else if(big_len==small_len)
{
    for(int i=0;i<small_len;i++)
    {
        if(small[i]!=big[i] && ++operations>1)
        {
            return false;
        }
    }
}

1개정도 차이

int i = 0;
while(i<small_len)
{
    if(small[i]!=big[i+operations])
    {
        if(++operations>1)
        {
            return false;
        }
    }
    i++;
}

solution

//http://codingdojang.com/scode/445?langby=%EA%B8%B0%20%ED%83%80
//https://www.careercup.com/question?id=4793416529477632

#include<stdio.h>

inline int mstrlen(char* s1)
{
    int i = 0;
    for (; s1[i]; i++);
    return i;
}

int OneEditApart(char* s1, char* s2)
{
    int s1_line = mstrlen(s1);
    int s2_line = mstrlen(s2);

    char* big   = s1_line < s2_line ? s2 : s1;
    char* small = s1_line < s2_line ? s1 : s2;

    int big_len   = mstrlen(big);
    int small_len = mstrlen(small);

    int operations = 0;

    if (big_len - small_len > 1)
    {
        return false;
    }
    else if(big_len==small_len)
    {
        for(int i=0;i<small_len;i++)
        {
            if(small[i]!=big[i] && ++operations>1)
            {
                return false;
            }
        }
    }
    else
    {
        int i = 0;
        while(i<small_len)
        {
            if(small[i]!=big[i+operations])
            {
                if(++operations>1)
                {
                    return false;
                }
            }

            i++;
        }
    }

    return true;
}

int main(void)
{
    printf("%s\n", OneEditApart("cat", "cut") == 1 ? "true" : "false");
    printf("%s\n", OneEditApart("cat", "cit") == 1 ? "true" : "false");
    printf("%s\n", OneEditApart("cat", "caz") == 1 ? "true" : "false");
    printf("%s\n", OneEditApart("cat", "czz") == 1 ? "true" : "false");
    printf("%s\n", OneEditApart("ztz", "czz") == 1 ? "true" : "false");
    printf("%s\n", OneEditApart("cat", "ccat") == 1 ? "true" : "false");

    return 0;
}