[Leetcode] 14. Longest Common Prefix

 

Identifying the Problem

주어진 단어들의 공통 접두사를 찾아 리턴한다.

Ex ) strs = ["flower","flow","flight"] -> output : fl

 

제한조건은 다음과 같다.

• 1 <= 단어의 개수 <= 200
• 0 <= 각 단어별 길이 <= 200
• 모든 strs[i] 는 소문자이다. 

Organizing thoughts

0. 단어가 하나이면 전체 return, 단어 중 " "이 있는 경우 return 0

1. 가장 짧은 단어의 길이를 구함

2. 그 길이만큼 반복하면서

0번째 1번째

1번째 2번째

2번째 3번째

... 비교하다가

서로 다른 경우가 있으면 바로 이전까지의 정답 return

Sourcecode

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

char * longestCommonPrefix(char ** strs, int strsSize){
 
    if (strsSize == 0) return ""; //0
    if (strsSize == 1) return strs[0]; //0
    
    char *answer = malloc(sizeof(char) * 200);
    strcpy(answer,"");
    
   
    int ss=0;
    int n[200] = {0,};
    
    ss= strlen(*strs);
    
    if(ss==0) return answer;  //0  
    
	for(int i=1;i<strsSize;i++) //1
	{
	    n[i] =strlen(strs[i]);
 	   if(ss>n[i])
 	   	ss = n[i];
    
	}    
    
         
	for(int i=0;i<ss;i++) //2
	{
  	 for(int k =0; k<strsSize-1 ; k++) 
 	  {
	   	if(strs[k][i] != strs[k+1][i])
	            	return answer;
   
   	}       
   
  	 strncat(answer,&(strs[0][i]),1);
	}     
    
    return answer;
}

 

Mistake

단어수가 3개인 줄 알고,

A=B, B=C -> A=C 논리를 써서 코드 작성했다가 단어 수가 3개 이상이 될 수 있었음을 늦게 알고,

갈아엎음.. 

New things learned

• strncat(answer,&(strs[0][i]),1) 에서 strcat 을 사용했으면 hello ello llo lo o 가 누적이 되었을 것이다. 
• strlen, strcat, strcpy 의 파라미터는 포인터 형으로 주어야 한다.
• 2차원 포인터 문자열을 사용할 때, s[j][k] 이런 식으로 하는 습관을 기르자
  굳이 하겠다면 *(*(ptr_ary+j)+k) 이런식으로 사용하면 된다.
• 문자열 포인터는 읽기 전용이기에 개별 요소를 변경하는 것은 불가능하다.
  *(str + 1) = 'z' (X)