Simple idea n^2 complexity


  • 0
    J
    class Solution {
    public:
    	string longestCommonPrefix(vector<string>& strs) {
    		string ret = "";
    		if (strs.empty())
    			return ret;
    		if (strs.size() == 1)
    			return strs[0];
    		bool found = false;
    		for (int i = 0; i < strs[0].length(); i++){//the i-th char of string
    			if (found)
    				break;
    			for (int j = 1; j < strs.size(); j++){//the j-th string
    				if (i >= strs[j].length()){
    					ret = strs[j];
    					found = true;
    					break;
    				}
    				else if (strs[j][i] != strs[j - 1][i]){
    					ret = strs[j].substr(0, i);
    					found = true;
    					break;
    				}
    				else{
    					ret = strs[j].substr(0, i + 1);
    					found = false;
    				}
    			}
    		}
    		return ret;
    	}
    };

  • 0
    J

    9 ms used. the idea is very simple


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.