LeetCode - 14.Longest Common Prefix

가장 긴 접두사 찾는 문제이다.

 

처음엔 한글자씩 뽑아서 일치하면 넘어가고 그런식으로 풀어나가려고 했는데, 한글자씩 뽑는건 되는데 체크하고 다음거 넘어가고, 틀리면 구문 탈출하는 과정이 복잡한거 같아서 생각을 바꿨다. 

 

아예 첫 글자를 기준으로 삼고, 뒤에서부터 하나씩 잘라가면서 비교하는게 나을거 같았다. 

왜냐하면 앞에서부터 글자를 비교하면 글자 length를 고려해야해서 복잡할거 같았다. 

 

class Solution 
{
public:
	string longestCommonPrefix(vector<string>& strs)
	{
		if (strs.empty()) return "";
		// 첫번째 단어를 기준으로 선택
		string prefix = strs[0];

		// 첫 번째 문자열을 제외하고 나머지 문자열을 순회
		for (int i = 1; i < strs.size(); i++)
		{
			// prefix의 단어와 일치하면 구문 탈출
			while (strs[i].find(prefix) != 0)
			{
				// 뒷부분에서부터 한개씩 자르기
				prefix = prefix.substr(0, prefix.length() - 1);
				// 첫번째 단어 다 지워졌을때 바로 탈출 
				if (prefix.empty()) return "";
			}
		}
		return prefix;
	}
};

 

그래서 뒷부분 부터 잘라가면서 모든 문자열에 공통적인 접두사를 찾는게 좋다고 생각해서 이런식으로 풀어봤다.

 

가장 빠른건 2차원 배열로, 각 문자열의 단어 하나하나를 순환하면서, 동일한 위치에 같은 문자가 있는지 확인하고, 없으면 바로 루프를 중단하고 지금까지의 문자열을 반환하는 코드였다. 

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
       string rez = "";
       int ct = 0;
        int i = 1;
           
            for(int j = 0; j < strs[0].size(); j++)
            { 
                for(int i = 1; i < strs.size();i++) 
                  if(strs[0][j] == strs[i][j])
                  { 
                   ct++;
                  }
                  if(ct == strs.size()-1)
                  {
                  rez += strs[0][j];
                  ct = 0;
                  }
                  else 
                    break;
            }
                
       return rez; 
    }
};

내가 생각하기에 가장 복잡할거 같은 코드가 제일 빠른 코드였다 ㅎㅎ;;; 

 

다음엔 생각해본건 꼭 구현해보고 다른 방식으로 도전해 봐야겠다 ㅠ