Leetcode - 最も長い共通プレフィックス - ランタイムがソリューションに比べて遅いのはなぜですか？

Question

質問：文字列の配列の中で最も長い共通接頭文字列を見つける関数を書く。

これはleetcodeからの簡単な質問です。以下は私のVSです。解決策の答え。問題は、私の答えがランタイムスピードの1.17％を上回り、ソリューションが79.65％を打つということです。 なぜコードが遅いのですか？

私たちのコードは、最初の共通文字列を操作し始めるまではほとんど同じです。これは、Stringクラスのindexofとsubstring関数を呼び出すことでこれを行い、私が定義したfindCommon関数を使用してそれを行います。

ソリューション：

 public String longestCommonPrefix(String[] strs) { 
      if(strs == null || strs.length == 0) return ""; 
      String pre = strs[0]; 
      int i = 1; 
      while(i < strs.length){ 
       while(strs[i].indexOf(pre) != 0) 
        pre = pre.substring(0,pre.length()-1); 
        i++; 
       } 
       return pre; 
     } 

これは私です：私の意見では

 public static String longestCommonPrefix(String[] strs){ 
     if(strs == null || strs.length == 0) 
      return ""; 
     String result = strs[0]; 
     for(int index = 1; index < strs.length; index++) 
      result = findCommon(result, strs[index]); 
     return result; 
    } 

    public static String findCommon(String a, String b){ 
     String common = ""; 
     for(int index = 0; index < Math.min(a.length(), b.length()); index++) 
     { 
      if(a.charAt(index) == b.charAt(index)) 
       common += a.charAt(index); 
      else 
       break; 
     } 
     return common; 
     } 

関数は文字列ライブラリで定義されているので、ソリューションのコードは単純に見えます。しかし、それは彼らが存在しないことを意味しません。

Answer 1

あなたは接頭辞文字列を構築しているかを見てみましょう：

 String common = ""; 
    for(int index = 0; index < Math.min(a.length(), b.length()); index++) 
    { 
     if(a.charAt(index) == b.charAt(index)) 
      common += a.charAt(index); 
     else 
      break; 
    } 
    return common; 

あなたは

common += a.charAt(index); 

Javaは新しいタックによって形成されたブランドの新しいStringオブジェクトを作成する必要がありますを実行するたびに文字を既存の文字列の末尾に追加します。commonつまり、長さpの接頭文字列を作成するコストはO（p ）になります。合計文字列がn個ある場合、プログラムのランタイムはO（np ）のようになります。基準溶液に対して

コントラストこれを：多くのJava実装で

pre = pre.substring(0,pre.length()-1); 

、サブストリングを作成する行為は、O（1）新たな文字列は元の文字列と基本となる文字列を共有することができるので、時間がかかり（いくつかの指数は新しい開始指数を説明するために微調整されている）。つまり、p接頭辞を使用する作業のコストは、O（p ）ではなくO（p）になり、長い文字列のパフォーマンスが大幅に向上する可能性があります。