[LeetCode] 7.Longest Common Prefix

leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

 

1. Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"] Output: "fl"

 

Example 2:

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

 

Constraints:

• 0 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

2. Code

package leetCode;

public class LogestCommonPrefix_easy { //앞에만 같으면 되는 중복값

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] strs = {"flower"};
		System.out.println(longestCommonPrefix(strs));
	}
	
	public static String longestCommonPrefix(String[] strs) {
		if(strs.length == 1) {
			return strs[0];
		}
		
		String result = "";
		
		for(int i = 0 ; i < strs.length; i++) {
			if(i == 0) {
				result = commonPrefix(strs[i], strs[i+1]);
				i++;
			} else {
				result = commonPrefix(result, strs[i]);
			}		
		}
		return result;
	}
	
	public static String commonPrefix(String s1, String s2) {
		String result = "";
		int shortSize = shortSize(s1, s2);
		for(int j = 0 ; j < shortSize; j++) {
			if(s1.charAt(j) == s2.charAt(j)) {
				result = result + s1.charAt(j);
			} else {
				break;
			}
		}
		return result;
	}
	
	public static int shortSize(String s1, String s2) {
		if(s1.length() <= s2.length()) {
			return s1.length();
		}
		return s2.length();
	}
}

 

3. Report

그냥 중복값인줄 알고 엄청 복잡하게 짰다가 수정했다

input이 String[] strs = {"reflower" , "flower", "flight"} 일때

output이 "fl"이 나오게 하는 줄 알았는데

앞에서부터 같은 문장 찾는거였다..

괜히 시간만 낭비 T^T

 

아쉬우니까 그냥 중복값 코드도 추가해본다

 

package leetCode;

import java.util.ArrayList;


public class LongestCommonPrefix {

	public static void main(String[] args) {
		String[] strs = {""};
		System.out.println(longestCommonPrefix(strs));
	}

	public static String longestCommonPrefix(String[] strs) {
        if(strs.length == 1) {
			return strs[0];
		}
		strs = ascArray(strs);
		//System.out.println(strs[0] + " " + strs[1] + " " + strs[2]);
		ArrayList<String> resultList = new ArrayList();

		//두개의 공통 string을 반환해주는 ArrayList를 이용하자!
		for(int i = 0; i < strs.length; i++) {
			if(i==0) {
				resultList = commonList(strs[i], strs[i+1]);
				i++;
				//resultList에는 flow가 들어있음
			} else {
				for(int j = 0; j < resultList.size(); j++) {//j=0일떄 fl, j=1일때 er
					if(!strs[i].contains(resultList.get(j))) {
						resultList.remove(j);
						j--;
					}
				}
			}		
		}
		if(resultList.size() == 0) {
			return "";
		}
		
		return resultList.get(0);
	}

	public static String[] ascArray(String[] strs) {
		for(int i = 0; i < strs.length-1; i++) {
			if(strs[i+1].length() < strs[i].length()) {
				String temp = strs[i];
				strs[i] = strs[i+1];
				strs[i+1] = temp;
			}
		}
		return strs;
	}

	public static ArrayList<String> commonList(String shortS, String longS){
		ArrayList al = new ArrayList(); //공통된걸 담은 ArrayList

		for(int i = 0; i < shortS.length(); i++) {
			for(int j = 0; j < i+1; j++) {
                String result = "";
				for(int k = j; k < shortS.length()-i+j; k++) {
					result = result + shortS.charAt(k); //sh[k];
				}
				if(longS.contains(result)) {
					al.add(result);
				}
			}		
		}
		return al;
	}
}

"flow"를 쪼갠다고 칠때

flow, flo, low, fl, lo , ow, f, l, o, w

이렇게 쪼개는데 무진장 고생했다..ㅎ

더 쉬운 방법이 있다고 들었는데 다음에 따라해보도록한다..

 

4. Learned

[자바 특정 문자열 포함 확인 및 찾기]

 

1) contains()   :  포함여부

String s = "hello"

if(s.contains("he")) = true

 

2) indexOf()   :  포함된 특정 문자나 문자열0 시작위치 인덱스 반환 (없으면 -1 반환)

String s = "helloWorld"

s.indexOf("Wo") = 5

 

3) mathces()  :  정규식을 이용하여 특정 문자 검색

 

자주쓰는 정규식 패턴

숫자만 : ^[0-9]*$
영문만 : ^[a-zA-Z]*$
영문만, 띄어쓰기가능 : /^[a-zA-Z\s]+$/
한글만 : ^[가-힣]*$
한글만,띄어쓰기가능 :  /^[가-힣\s]+$/
한글 & 영문만 : /^[가-힣a-zA-Z]+$/;
영문 & 숫자만 : ^[a-zA-Z0-9]*$
E-Mail : ^[a-zA-Z0-9]+@[a-zA-Z0-9]+$
휴대폰 : ^01(?:0|1|[6-9]) - (?:\d{3}|\d{4}) - \d{4}$
일반전화 : ^\d{2,3} - \d{3,4} - \d{4}$
URL : /^(file|gopher|news|nntp|telnet|https?|ftps?|sftp):\/\/([a-z0-9-]+\.)+[a-z0-9]{2,4}.*$/
주민등록번호 : \d{6} \- [1-4]\d{6}
IP 주소 : ([0-9]{1,3}) \. ([0-9]{1,3}) \. ([0-9]{1,3}) \. ([0-9]{1,3})