[LeetCode] Longest common prefix

단어가 들어있는 String 배열에서 가장 긴 공통된 접두어를 구하라.

 sudo code
        가장 긴 단어와 가장 짧은 단어를 고르고
        가장 짧은 단어의 길이만큼 긴 단어의 앞에서 부터 비교
        차감하면서 비교
        같지 않다면 "" 리턴

1차 시도있는 String 배열에서 가장 긴 공통된 접두어를 구하라.

 

 sudo code

        가장 긴 단어와 가장 짧은 단어를 고르고

        가장 짧은 단어의 길이만큼 긴 단어의 앞에서 부터 비교

        차감하면서 비교

        같지 않다면 "" 리턴

1차 시도

class Solution {
    public String getShortestWord(String[] strs) {
        
        if (strs == null || strs.length < 1) {
            return "";
        }
        String shortestWord = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < shortestWord.length()) {
                shortestWord = strs[i];
            }
        }
            return shortestWord;
    }
    public String getLongestWord(String[] strs) {
        if(strs == null || strs.length < 1) {
            return "";
        }
        String longestWord = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if(strs[i].length() > longestWord.length()) {
                longestWord = strs[i];
            }
        }
        return longestWord;
    }
    public String longestCommonPrefix(String[] strs) {
        /*
        sudo code
        가장 긴 단어와 가장 짧은 단어를 고르고
        가장 짧은 단어의 길이만큼 긴 단어의 앞에서 부터 비교
        차감하면서 비교
        같지 않다면 "" 리턴
        */
        String shortword = getShortestWord(strs);
        String longword = getLongestWord(strs);
        
        if(shortword == "" || longword == "") {
            return "";   
        }else {
            for(int idx = shortword.length(); idx > 0; idx--) {
                if(longword.startsWith(shortword)) {
                    return shortword;
                }else {
                    shortword = shortword.substring(0, shortword.length()-1);
                }
            }    
        }
        return "";
    }
}

 

 

음 brute force로 200개 단어 앞글자부터 대조해가면서 answer를 만들어야 하나

 

2차시도

class Solution {
    public int getShortestWord(String[] strs) {
        int idx = 0;
        
        if (strs == null || strs.length < 1) {
            return idx;
        }
        String shortestWord = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < shortestWord.length()) {
                shortestWord = strs[i];
                idx = i;
            }
        }
            return idx;
    }
    
    public String longestCommonPrefix(String[] strs) {
        /*
        sudo code
        가장 짧은 단어를 고르고
        그 단어의 길이만큼 나머지 단어를 앞에서 부터 비교
        */
        int shortIdx = getShortestWord(strs);
        if(shortIdx == 0) {
            return "";
        }else {
            String shortword = strs[shortIdx];
        }
        
        
        if(shortword.length() == 0) {
            return "";   
        }else {
            for(int idx = shortword.length(); idx > 0; idx--) {
                for(int i = 0; i < strs.length; i++) {
                    if(!strs[i].startsWith(shortword)) {
                        shortword = shortword.substring(0, shortword.length() - 1);
                    } else {
                        if(i == strs.length - 1) return shortword;
                    }
                }
            }
        }
        return "";
    }
}
error case 
["a"]

 

3차시도

class Solution {
    public int getShortestWord(String[] strs) {
        int idx = 0;
        
        if (strs == null || strs.length < 1) {
            return idx;
        }
        String shortestWord = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < shortestWord.length()) {
                shortestWord = strs[i];
                idx = i;
            }
        }
            return idx;
    }
    
    public String longestCommonPrefix(String[] strs) {
        /*
        sudo code
        가장 짧은 단어를 고르고
        그 단어의 길이만큼 나머지 단어를 앞에서 부터 비교
        */
        int strsLength = strs.length;
        if(strsLength < 2) {
            if(strsLength == 0) return "";
            else return strs[0];
        }
        int shortIdx = getShortestWord(strs);
        String shortword = "";
        if(shortIdx == 0) {
            return "";
        }else {
            shortword = strs[shortIdx];
        }
        
        
        if(shortword.length() == 0) {
            return "";   
        }else {
            for(int idx = shortword.length(); idx >=0; idx--) {
                String temp = shortword;
                for(int i = strs.length -1; i >= 0; i--) {
                    if(!strs[i].startsWith(shortword)) {
                        shortword = shortword.substring(0, shortword.length() - 1);
                    }
                }
                if(temp.equals(shortword)) return shortword;
            }
        }
        return "";
    }
}
error case
Input ["cir","car"]
Output ""
Expected "c"

 

4차시도

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        else if (strs.length == 1) return strs[0];
        else {
            String temp = "";
            int idx = 0;
            boolean flag = true;
            while(idx < strs[0].length()) {
                if(strs[0].length() < 1) return "";
                temp += strs[0].charAt(idx);
                for(int i = 1; i <strs.length; i++) {
                    flag = strs[i].startsWith(temp);
                    if(!flag) break;
                }
                if(flag) idx++;
                else{
                    return strs[0].substring(0, idx);
                }
            }
            return strs[0];
        }
    }
}

[flower, flower, flower, flower] 에서 안되서 
while(flag), return "" -> 
while(idx < strs[0].length())

Runtime: 10 ms, faster than 7.22% of Java online submissions for Longest Common Prefix.
Memory Usage: 39.1 MB, less than 8.63% of Java online submissions for Longest Common Prefix.
return strs[0]; 추가

 

스터디원 분의 도움을 받아 가장 짧은 단어로 접근한 코드로 변경

import java.util.*;

class Solution {
    public int getShortestWordIdx(String[] strs) {
        int idx = 0;
        
        if (strs == null || strs.length < 1) {
            return idx;
        }
        String shortestWord = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < shortestWord.length()) {
                shortestWord = strs[i];
                idx = i;
            }
        }
            return idx;
    }
    
    public String[] removeShortestWord(String[] strs, int idx) {
        ArrayList<String> temp = new ArrayList<>();
        for(int i = 0; i < strs.length; i++){
            if(i != idx){
                temp.add(strs[i]);
            }
        }
        return temp.toArray(new String[temp.size()]);
    }
    
    public String longestCommonPrefix(String[] strs) {
        int strsLength = strs.length;
        if(strsLength < 2) {
            if(strsLength == 0) return "";
            else return strs[0];
        }
        int shortIdx = getShortestWordIdx(strs);
        String shortestWord = strs[shortIdx];
        int shortLength = shortestWord.length();
        if(shortestWord.equals("") || shortLength == 0) return shortestWord;

        String[] removeShortWordArray = removeShortestWord(strs, shortIdx);
        
        for(int i = 0; i < removeShortWordArray.length; i++) {
            for(int j = shortLength -1; j >= 0; j--){
                if(!removeShortWordArray[i].startsWith(shortestWord)) {
                    shortestWord = shortestWord.substring(0, j);
                }
            }
        }
        
        return shortestWord;
    }
}

Runtime: 4 ms, faster than 21.23% of Java online submissions for Longest Common Prefix.
Memory Usage: 36.7 MB, less than 97.50% of Java online submissions for Longest Common Prefix.